2 problems found
From the facts \begin{alignat*}{2} 1 & \quad=\quad & & 0\\ 2+3+4 & \quad=\quad & & 1+8\\ 5+6+7+8+9 & \quad=\quad & & 8+27\\ 10+11+12+13+14+15+16 & \quad=\quad & & 27+64 \end{alignat*} guess a general law. Prove it. Hence, or otherwise, prove that \[ 1^{3}+2^{3}+3^{3}+\cdots+N^{3}=\tfrac{1}{4}N^{2}(N+1)^{2} \] for every positive integer \(N\). [Hint. You may assume that \(1+2+3+\cdots+n=\frac{1}{2}n(n+1)\).]
Solution: \begin{align*} && (n^2+1) + (n^2+2) + \cdots + (n+1)^2 &= n^3+(n+1)^3 \\ \Leftrightarrow && \sum_{i=n^2+1}^{(n+1)^2} i &= n^3 + (n+1)^3 \\ && \sum_{i=n^2+1}^{(n+1)^2} i &= \sum_{i=1}^{(n+1)^2} i- \sum_{i=1}^{n^2} i \\ &&&= \frac{(n+1)^2((n+1)^2+1)}{2} - \frac{n^2(n^2+1)}{2} \\ &&&= \frac{(n+1)^2(n^2+2n+2) - n^2(n^2+1)}{2} \\ &&&= \frac{2(n+1)^3+n^2(n^2+2n+1) - n^2(n^2+1)}{2}\\ &&&= \frac{2(n+1)^3+2n^3 + n^2(n^2+1) - n^2(n^2+1)}{2}\\ &&&= (n+1)^3+n^3 \end{align*} \begin{align*} && \sum_{i=1}^{N^2} i &=(0^3+1^3)+ (1^3+2^3)+(2^3+3^3) + \cdots + ((N-1)^3+N^3) \\ &&&= 2 \left (1^3+2^3 + 3^3 + \cdots + (N-1)^3 \right) + N^3 \\ \Rightarrow && \sum_{i=1}^N i^3 &= \frac12 \left ( N^3+ \sum_{i=1}^{N^2} i \right) \\ &&&= \frac12 \left ( N^3 + \frac{N^2(N^2+1)}{2} \right) \\ &&&= \frac{N^2(N^2+1)+2N^3}{4} \\ &&&= \frac{N^2(N^2+2N+1)}{4} \\ &&&= \frac{N^2(N+1)^2}{4} \\ \end{align*}
A set of \(2N+1\) rods consists of one of each length \(1,2,\ldots,2N,2N+1\), where \(N\) is an integer greater than 1. Three different rods are selected from the set. Suppose their lengths are \(a,b\) and \(c\), where \(a > b > c\). Given that \(a\) is even and fixed, show, by considering the possible values of \(b\), that the number of selections in which a triangle can then be formed from the three rods is \[ 1+3+5+\cdots+(a-3), \] where we allow only non-degenerate triangles (i.e. triangles with non-zero area). Similarly obtain the number of selections in which a triangle may be formed when \(a\) takes some fixed odd value. Write down a formula for the number of ways of forming a non-degenerate triangle and verify it for \(N=3\). Hence show that, if three rods are drawn at random without replacement, then the probability that they can form a non-degenerate triangle is \[ \frac{(N-1)(4N+1)}{2(4N^{2}-1)}. \]
Solution: Suppose we have \(a = 2k\), it is necessary (by the triangle inequality) that \(b + c > a\). So the smallest \(b\) can be is \(k+1\), and then \(c\) must be \(k\) (1 choice). Then \(b\) could be \(k+2\) and \(c\) can be \(k+1\), \(k\), \(k-1\) (3 choices). Suppose \(b = k+i\) then \(c\) can be \(k+i-1, \ldots, k-i+1\) which is \(2i-1\) choices. This works until \(b = 2k-1\) and there are \(2(k-1)-1 = 2k-3 = a-3\) choices. Therefore there are \(1 + 3 + 5 + \cdots + (a-3)\) total choices. If \(a = 2k+1\) then, \(b = k+1\) is not possible \(b = k+2\) we have \(a = k+1, k\) (2 choices) \(b = k+3\) we have \(a = k+2, k+1, k, k-1\) (4 choices) \(b = k + i\) we have \(a = k+i-1, \cdots, k-i+2\) (\(2i-2\) choices) This works until \(b = k+k\) with \(2k-2 = a-3\) choices. So \(2 + 4 + \cdots + (a-3)\) If \(a\) is even, we have \(\left ( \frac{a-2}{2} \right)^2\) If \(a\) is odd we have \(\frac{(a-3)(a-1)}{4}\) Therefore the total number is: \begin{align*} C &= \sum_{k=2}^N \left ( \frac{(2k-2)^2}{4} + \frac{(2k+1-3)(2k+1-1)}{4} \right) \\ &= \sum_{k=2}^N \left ( (k-1)^2 + (k-1)k\right) \\ &= \sum_{k=2}^N (2k^2-3k+1) \\ &= \sum_{k=1}^N (2k^2-3k+1) \\ &= \frac{N(N+1)(2N+1)}{3} - \frac{3N(N+1)}{2} + N \\ &= \frac{N((N+1)(4N+2-9)+6)}{6} \\ &= \frac{N(4N+1)(N-1)}{6} \\ \end{align*} When \(N = 3\) we have \(1, 2, \cdots, 7\) sticks, and so \(a = 4\), \(1\) option \(a = 5\), \(2\) options \(a = 6\) \(4\) options \(a = 7\) \(6\) options for a total of \(13\). \(\frac{3 \cdot 13 \cdot 2}{6} = 13\) so this is promising, There are \(\binom{2N+1}{3}\) ways to choose three sticks (in order) and of those our formula tells us how many are valid, therefore \begin{align*} && P &= \frac{ \frac{N(4N+1)(N-1)}{6} }{\frac{(2N+1)2N(2N-1)}{6}} \\ &&&= \frac{(4N+1)(N-1)}{2(4N^2-1)} \end{align*}