• About
• Statistics
• Number Theory
• Java
• Data Structures
• Cornerstones
• Calculus

Exercises - Induction and Sums

Part I

Use mathematical induction to prove the following statements hold for every positive integer $n$.

1. $\displaystyle{\sum_{i=1}^{n} i = \frac{n(n+1)}{2}}$  

   Let us argue by induction...

   Starting with the basis step, we must show that the statement holds for the smallest value of $n$ that we wish to consider.

   Since we seek to prove the statement holds for every positive integer, then the smallest value we wish to consider would be $n=1$.

   When $n=1$, the left side collapses to a "sum" containing only a single term: $$\sum_{i=1}^n i = 1$$

   While on the right side, if $n=1$, $$\frac{n(n+1)}{2} = \frac{1(1+1)}{2} = 1$$

   Since the left and right sides agree in value, the statement is true when $n=1$

   Now we proceed with the inductive step, where we must show that if we know the statement holds for some particular value of $n$, say $n=k$, then the statement must also hold when $n=k+1$.

   Equivalently for this problem, we need to show if the following "inductive hypothesis" is true $$\sum_{i=1}^k i = \frac{k(k+1)}{2}$$ then it must also be true that $$\sum_{i=1}^{k+1} i = \frac{(k+1)((k+1)+1)}{2}$$

   To this end, we will attempt to manipulate the left side of the above equation until it looks like the right side. We can use the inductive hypothesis to provide the transition from an expression involving $\sum$ to a simpler algebraic expression.

   $$\begin{array}{rcl} \sum_{i=1}^{k+1} i &=& \left( \sum_{i=1}^{k} i \right) + (k+1)\\\\ &=& \left( \frac{k(k+1)}{2} \right) + (k+1)\\\\ &=& \frac{k}{2}(k+1) + (k+1)\\\\ &=& (k+1) \left( \frac{k}{2} + 1\right)\\\\ &=& (k+1) \left( \frac{k+2}{2} \right)\\\\ &=& \frac{(k+1)(k+2)}{2}\\\\ &=& \frac{(k+1)((k+1)+1)}{2} \end{array}$$

   Having met with success in both the basis and inductive steps, we are free to conclude by the principle of mathematical induction, that the following is true for every positive integer $n$: $$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$

   QED.

2. $\displaystyle{\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}}$  

   Let's argue by induction...

   Starting with the basis step...

   We must show that the statement holds for the smallest value of $n$ that we wish to consider.

   Since we seek to prove the statement holds for every positive integer, then the smallest value we wish to consider would be $n=1$.

   When $n=1$, the left side collapses to a "sum" containing only a single term: $$\sum_{i=1}^n i^2 = 1^2 = 1$$

   While on the right side, if $n=1$, we have $$\frac{n(n+1)(2n+1)}{6} = \frac{1(1+1)(2 \cdot 1 + 1)}{6} = \frac{2 \cdot 3}{6} = 1$$

   Since the left and right sides agree in value, the statement is true when $n=1$

   Now we proceed with the inductive step...

   We must show that if we know the statement holds for some particular value of $n$, say $n=k$, then the statement must also hold when $n=k+1$.

   Equivalently for this problem, we need to show if the following "inductive hypothesis" is true for some value $k$ $$\sum_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}$$ then $$\sum_{i=1}^{k+1} i = \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}$$

   To this end, we will attempt to manipulate the left side of the above equation until it looks like the right side. We can use the inductive hypothesis to provide the transition from an expression involving $\sum$ to a simpler algebraic expression.

   $$\begin{array}{rcl} \sum_{i=1}^{k+1} i^2 &=& \left( \sum_{i=1}^{k} i^2 \right) + (k+1)^2\\\\ &=& \left( \frac{k(k+1)(2k+1)}{6} \right) + (k+1)^2\\\\ &=& \frac{k(k+1)(2k+1)+6(k+1)^2}{6}\\\\ &=& \frac{(k+1)[(k(2k+1)+6(k+1)]}{6}\\\\ &=& \frac{(k+1)(2k^2 +7k +6)}{6}\\\\ &=& \frac{(k+1)(k+2)(2k+3)}{6}\\\\ &=& \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}\\\\ \end{array}$$

   Having met with success in both the basis and inductive steps, we can conclude by the principle of mathematical induction that the following must then be true for every positive integer $n$. $$\displaystyle{\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}}$$

   QED.

3. $\displaystyle{\sum_{i=1}^{n} i^3 = \frac{n^2 (n+1)^2}{4}}$  

   Let's argue by induction...

   Starting with the basis step...

   We must show that the statement holds for the smallest value of $n$ that we wish to consider.

   Since we seek to prove the statement holds for every positive integer, then the smallest value we wish to consider would be $n=1$.

   When $n=1$, the left side collapses to a "sum" containing only a single term: $$\sum_{i=1}^n i^3 = 1^3 = 1$$

   While on the right side, if $n=1$, we have $$\frac{1^2 (1+1)^2}{4} = \frac{1 \cdot 2^2}{4} = 1$$

   Since the left and right sides agree in value, the statement is true when $n=1$.

   Now we proceed with the inductive step...

   We must show that if we know the statement holds for some particular value of $n$, say $n=k$, then the statement must also hold when $n=k+1$.

   Equivalently for this problem, we need to show if the following "inductive hypothesis" is true for some value $k$ $$\sum_{i=1}^{k} i^3 = \frac{k^2 (k+1)^2}{4}$$ then $$\sum_{i=1}^{k+1} i^3 = \frac{(k+1)^2 [(k+1)+1]^2}{4}$$

   To this end, we will attempt to manipulate the left side of the above equation until it looks like the right side. We can use the inductive hypothesis to provide the transition from an expression involving $\sum$ to a simpler algebraic expression.

   $$\begin{array}{rcl} \sum_{i=1}^{k+1} i^3 &=& \left( \sum_{i=1}^{k} i^3 \right) + (k+1)^3\\\\ &=& \left( \frac{k^2 (k+1)^2}{4} \right) + (k+1)^3\\\\ &=& (k+1)^2 \left[ \frac{k^2}{4} + (k+1) \right]\\\\ &=& (k+1)^2 \cdot \frac{k^2 + 4(k+1)}{4}\\\\ &=& (k+1)^2 \cdot \frac{k^2 + 4k + 4}{4}\\\\ &=& (k+1)^2 \cdot \frac{(k+2)^2}{4}\\\\ &=& \frac{(k+1)^2[(k+1)+1]^2}{4}\\\\ \end{array}$$

   Having met with success in both the basis and inductive steps, we can conclude by the principle of mathematical induction that the following must then be true for every positive integer $n$. $$\displaystyle{\sum_{i=1}^{n} i^3 = \frac{n^2 (n+1)^2}{4}}$$

   QED.

4. $\displaystyle{\sum_{i=1}^{n} i^4 = \frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}}$  

   Let's argue by induction...

   Starting with the basis step...

   We must show that the statement holds for the smallest value of $n$ that we wish to consider.

   Since we seek to prove the statement holds for every positive integer, then the smallest value we wish to consider would be $n=1$.

   When $n=1$, the left side collapses to a "sum" containing only a single term: $$\sum_{i=1}^n i^4 = 1^4 = 1$$

   While on the right side, if $n=1$, we have $$\frac{1^5}{5}+\frac{1^4}{2}+\frac{1^3}{3}-\frac{1}{30} = \frac{6+15+10-1}{30} = \frac{30}{30} = 1$$

   Since the left and right sides agree in value, the statement is true when $n=1$

   Now we proceed with the inductive step...

   We must show that if we know the statement holds for some particular value of $n$, say $n=k$, then the statement must also hold when $n=k+1$.

   Equivalently for this problem, we need to show if the following "inductive hypothesis" is true for some value $k$ $$\sum_{i=1}^{k} i^4 = \frac{k^5}{5}+\frac{k^4}{2}+\frac{k^3}{3}-\frac{k}{30}$$ then $$\sum_{i=1}^{k+1} i^4 = \frac{(k+1)^5}{5}+\frac{(k+1)^4}{2}+\frac{(k+1)^3}{3}-\frac{(k+1)}{30}$$

   Rather than try to directly manipulate the left side until it looks like the right side (although with patience, this could be done), we attempt to simplify both the left and right sides to the same algebraic expression.

   First we work with the left side... (note, we use the inductive hypothesis to provide the transition from the expression involving a $\sum$ to a simpler algebraic expression.)

                   $\displaystyle{\sum_{i=1}^{k+1} i^4}$ $$\begin{array}{rcl} &=& \left( \sum_{i=1}^{k} i^4 \right) + (k+1)^4\\\\ &=& \left( \frac{k^5}{5}+\frac{k^4}{2}+\frac{k^3}{3}-\frac{k}{30} \right) + (k+1)^4\\\\ &=& \frac{1}{30} \cdot [6k^5+15k^4+10k^3-k+30(k^4+4k^3+6k^2+4k+1)]\\\\ &=& \frac{1}{30} \cdot (6k^5+45k^4+130k^3+180k^2+119k+30)\\\\ \end{array}$$

   Now we work with the right side...

           $\displaystyle{\frac{(k+1)^5}{5}+\frac{(k+1)^4}{2}+\frac{(k+1)^3}{3}-\frac{(k+1)}{30}}$

   $$\begin{array}{rcl} &=& \frac{k^5+5k^4+10k^3+10k^2+5k+1}{5}+\frac{k^4+4k^3+6k^2+4k+1}{2} \cdots\\ & & + \, \frac{k^3+3k^2+3k+1}{3}-\frac{k+1}{30}\\\\ &=& \frac{6k^5+30k^4+60k^3+60k^2+30k+6}{30}+\frac{15k^4+60k^3+90k^2+60k+15}{30} \cdots\\ & & + \, \frac{10k^3+30k^2+30k+10}{30}-\frac{k+1}{30}\\\\ &=& \frac{1}{30} \cdot (6k^5+45k^4+130k^3+180k^2+119k+30)\\\\ \end{array}$$

   Since we arrived at the same expression in both cases, we can conclude that $$\sum_{i=1}^{k+1} i^4 = \frac{(k+1)^5}{5}+\frac{(k+1)^4}{2}+\frac{(k+1)^3}{3}-\frac{(k+1)}{30}$$ which is what we needed to show in the inductive step.

   Having met with success in both the basis and inductive steps, we can conclude by the principle of mathematical induction that the following must then be true for every positive integer $n$. $$\sum_{i=1}^{n} i^4 = \frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}$$

   QED.

5. $1 + 2 + 2^2 + 2^3 + \cdots + 2^{n-1} = 2^n - 1$  

   The base case is easily established as when $n=1$, the left and right sides are both $1$. Now assume $1 + 2 + 2^2 + 2^3 + \cdots + 2^{k-1} = 2^k - 1$ for some integer $k$. Note that $$\begin{align*} 1 + 2 + 2^2 + 2^3 + \cdots + 2^{k-1} + 2^k &= 2^k - 1 + 2^k\\ &= 2 \cdot 2^2 - 1\\ &= 2^{k+1} - 1 \end{align*}$$ Hence, by the principle of mathematical induction, the claim holds.

Part II

Prove the following statements hold for every positive integer $n$ in two ways: 1) with mathematical induction; and 2) using the results proven in problems 1-4 above.

5. $\displaystyle{\sum_{i=1}^{n} (2i-1) = n^2}$  

   One Solution:

   Let us argue by induction...

   Starting with the basis step, we must show that the statement holds for the smallest value of $n$ that we wish to consider.

   Since we seek to prove the statement holds for every positive integer, then the smallest value we wish to consider would be $n=1$.

   When $n=1$, the left side collapses to a "sum" containing only a single term: $$\sum_{i=1}^n (2i-1) = 2\cdot1 - 1 = 1$$

   While on the right side, if $n=1$, $$n^2 = 1^2 = 1$$

   Since the left and right sides agree in value, the statement is true when $n=1$

   Now we proceed with the inductive step, where we must show that if we know the statement holds for some particular value of $n$, say $n=k$, then the statement must also hold when $n=k+1$.

   Equivalently for this problem, we need to show if the following "inductive hypothesis" is true $$\sum_{i=1}^k (2i-1) = k^2$$ then it must also be true that $$\sum_{i=1}^{k+1} (2i-1) = (k+1)^2$$

   To this end, we will attempt to manipulate the left side of the above equation until it looks like the right side. We can use the inductive hypothesis to provide the transition from an expression involving $\sum$ to a simpler algebraic expression.

   $$\begin{array}{rcl} \sum_{i=1}^{k+1} (2i-1) &=& \left( \sum_{i=1}^{k} (2i-1) \right) + 2(k+1)-1\\\\ &=& k^2 + 2(k+1) - 1\\\\ &=& k^2 + 2k + 2 - 1\\\\ &=& k^2 + 2k + 1\\\\ &=& (k+1)^2\\\\ \end{array}$$

   Having met with success in both the basis and inductive steps, we are free to conclude by the principle of mathematical induction, that the following is true for every positive integer $n$: $$\sum_{i=1}^n (2i-1)= n^2$$

   QED.

   ---

   A Second Solution:

   If we are allowed to appeal to the fact that $$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$$ then we can argue the result directly with the following: $$\begin{array}{rcl} \sum_{i=1}^{k}(2i-1) &=& \left[ \sum_{i=1}^n 2i \right] - \left[ \sum_{i=1}^n 1 \right]\\\\ &=& 2 \left[ \sum_{i=1}^n i \right] - n\\\\ &=& 2 \left[ \frac{n(n+1)}{2} \right] -n\\\\ &=& n(n+1) - n\\\\ &=& n^2 + n - n\\\\ &=& n^2\\\\ \end{array}$$ QED.

6. $\displaystyle{\sum_{i=1}^{n} 2i = n^2 + n}$  

   One Solution:

   Let us argue by induction...

   Starting with the basis step, we must show that the statement holds for the smallest value of $n$ that we wish to consider.

   Since we seek to prove the statement holds for every positive integer, then the smallest value we wish to consider would be $n=1$.

   When $n=1$, the left side collapses to a "sum" containing only a single term: $$\sum_{i=1}^n 2i = 2\cdot1 = 2$$

   While on the right side, if $n=1$, $$n^2 + n= 1^2 + 1 = 2$$

   Since the left and right sides agree in value, the statement is true when $n=1$

   Now we proceed with the inductive step, where we must show that if we know the statement holds for some particular value of $n$, say $n=k$, then the statement must also hold when $n=k+1$.

   Equivalently for this problem, we need to show if the following "inductive hypothesis" is true $$\sum_{i=1}^k 2i = k^2+k$$ then it must also be true that $$\sum_{i=1}^{k+1} 2i = (k+1)^2 + (k+1)$$

   To this end, we will attempt to manipulate the left side of the above equation until it looks like the right side. We can use the inductive hypothesis to provide the transition from an expression involving $\sum$ to a simpler algebraic expression.

   $$\begin{array}{rcl} \sum_{i=1}^{k+1} 2i &=& \left( \sum_{i=1}^{k} 2i \right) + 2(k+1)\\\\ &=& k^2 + k + 2(k+1)\\\\ &=& k^2 + k + 2k + 2 \\\\ &=& (k^2 + 2k + 1) + (k + 1)\\\\ &=& (k+1)^2 + (k+1)\\\ \end{array}$$

   Having met with success in both the basis and inductive steps, we are free to conclude by the principle of mathematical induction, that the following is true for every positive integer $n$: $$\sum_{i=1}^n 2i= n^2+n$$

   QED.

   ---

   A Second Solution:

   If we are allowed to appeal to the fact that $$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$$ then we can argue the result directly with the following: $$\begin{array}{rcl} \sum_{i=1}^{k}2i &=& 2 \left[ \sum_{i=1}^n i \right]\\\\ &=& 2 \left[ \frac{n(n+1)}{2} \right]\\\\ &=& n(n+1)\\\\ &=& n^2 + n\\\\ \end{array}$$ QED.

7. $\displaystyle{\sum_{i=1}^{n} (2i-1)^2 = \frac{4n^3-n}{3}}$  

   One Solution:

   Let us argue by induction...

   Starting with the basis step, we must show that the statement holds for the smallest value of $n$ that we wish to consider.

   Since we seek to prove the statement holds for every positive integer, then the smallest value we wish to consider would be $n=1$.

   When $n=1$, the left side collapses to a "sum" containing only a single term: $$\sum_{i=1}^n (2i-1)^2 = (2\cdot1-1)^2 = 1^2 = 1$$

   While on the right side, if $n=1$, $$\frac{4n^3-n}{3} = \frac{4 \cdot 1^3 - 1}{3} = \frac{3}{3} = 1$$

   Since the left and right sides agree in value, the statement is true when $n=1$

   Now we proceed with the inductive step, where we must show that if we know the statement holds for some particular value of $n$, say $n=k$, then the statement must also hold when $n=k+1$.

   Equivalently for this problem, we need to show if the following "inductive hypothesis" is true $$\sum_{i=1}^k (2i-1)^2 = \frac{4k^3-k}{3}$$ then it must also be true that $$\sum_{i=1}^{k+1} (2i-1)^2 = \frac{4(k+1)^3-(k+1)}{3}$$

   To this end, we will attempt to manipulate independently the left and right sides of the above equation until they appear identical. We can use the inductive hypothesis to provide a transition from an expression involving $\sum$ to a simpler algebraic expression.

   First we work with the left side...

   $$\begin{array}{rcl} \sum_{i=1}^{k+1} (2i-1)^2 &=& \left( \sum_{i=1}^{k} (2i-1)^2 \right) + (2(k+1)-1)^2\\\\ &=& \frac{4k^3-k}{3} + (2(k+1)-1)^2\\\\ &=& \frac{4k^3-k}{3} + (2k+1)^2\\\\ &=& \frac{1}{3} [4k^3 - k + 3(2k+1)^2]\\\\ &=& \frac{1}{3} [4k^3 - k + 3(4k^2 + 4k + 1)]\\\\ &=& \frac{1}{3} (4k^3 + 12k^2 + 11k + 3)\\\\ \end{array}$$

   Now we work with the right side...

   $$\begin{array}{rcl} \frac{4(k+1)^3-(k+1)}{3} &=& \frac{1}{3}[4(k+1)^3 - (k+1)]\\\\ &=& \frac{1}{3} [4(k^3 + 3k^2 + 3k + 1) - (k+1)]\\\\ &=& \frac{1}{3} (4k^3 + 12k^2 + 11k + 3)\\\\ \end{array}$$

   Finding these two expressions equal to the same expression, they must be equal to each other. In other words, $$\sum_{i=1}^{k+1} (2i-1)^2 = \frac{4(k+1)^3-(k+1)}{3}$$ which is what we needed to show.

   Having met with success in both the basis and inductive steps, we are free to conclude by the principle of mathematical induction, that the following is true for every positive integer $n$: $$\sum_{i=1}^{n} (2i-1)^2 = \frac{4n^3-n}{3}$$

   QED.

   ---

   A Second Solution:

   If we are allowed to appeal to the following facts: $$\sum_{i=1}^{n} i = \frac{n(n+1)}{2} \quad \textrm{and} \quad \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$$ then we can argue the result directly with the following: $$\begin{array}{rcl} \sum_{i=1}^{n} (2i-1)^2 &=& \sum_{i=1}^{n} (4i^2 - 4i + 1)\\\\ &=& \left[\sum_{i=1}^{n} 4i^2 \right] - \left[\sum_{i=1}^{n} 4i \right] + \left[\sum_{i=1}^{n} 1 \right]\\\\ &=& 4 \left[\sum_{i=1}^{n} i^2 \right] - 4 \left[ \sum_{i=1}^{n} i \right] + n\\\\ &=& 4 \left[\frac{n(n+1)(2n+1)}{6} \right] - 4 \left[ \frac{n(n+1)}{2} \right] + n\\\\ &=& \frac{2n(n+1)(2n+1)}{3} - \frac{6n(n+1)}{3} + \frac{3n}{3}\\\\ &=& \frac{4n^3+6n^2+2n-6n^2-6n+3n}{3}\\\\ &=& \frac{4n^3-n}{3}\\\\ \end{array}$$ QED.

8. $\displaystyle{\sum_{i=1}^{n} i(i+1) = \frac{n (n+1) (n+2)}{3}}$  

   One Solution:

   Let us argue by induction...

   Starting with the basis step, we must show that the statement holds for the smallest value of $n$ that we wish to consider.

   Since we seek to prove the statement holds for every positive integer, then the smallest value we wish to consider would be $n=1$.

   When $n=1$, the left side collapses to a "sum" containing only a single term: $$\sum_{i=1}^n i(i+1) = 1 \cdot (1+1) = 2$$

   While on the right side, if $n=1$, $$\frac{n(n+1)(n+2)}{3} = \frac{1 \cdot (1 + 1) \cdot (1+2)}{3} = \frac{2 \cdot 3}{3} = 2$$

   Since the left and right sides agree in value, the statement is true when $n=1$

   Now we proceed with the inductive step, where we must show that if we know the statement holds for some particular value of $n$, say $n=k$, then the statement must also hold when $n=k+1$.

   Equivalently for this problem, we need to show if the following "inductive hypothesis" is true $$\sum_{i=1}^k i(i+1) = \frac{k(k+1)(k+2)}{3}$$ then it must also be true that $$\sum_{i=1}^{k+1} i(i+1) = \frac{(k+1)[(k+1)+1][(k+1)+2]}{3}$$

   To this end, we will attempt to manipulate the left side above until it is identical to the right side. We can use the inductive hypothesis to provide a transition from an expression involving $\sum$ to a simpler algebraic expression.

   $$\begin{array}{rcl} \sum_{i=1}^{k+1} i(i+1) &=& \left( \sum_{i=1}^{k} i(i+1) \right) + (k+1)[(k+1)+1]\\\\ &=& \left( \frac{k(k+1)(k+2)}{3} \right) + (k+1)(k+2)\\\\ &=& (k+1)(k+2) \left( \frac{k}{3} + 1 \right)\\\\ &=& (k+1)(k+2) \left( \frac{k+3}{3} \right)\\\\ &=& \frac{(k+1)(k+2)(k+3)}{3}\\\\ &=& \frac{(k+1)[(k+1)+1][(k+1)+2]}{3} \end{array}$$

   Having met with success in both the basis and inductive steps, we are free to conclude by the principle of mathematical induction, that the following is true for every positive integer $n$: $$\sum_{i=1}^{n} i(i+1) = \frac{n(n+1)(n+2)}{3}$$

   QED.

   ---

   A Second Solution:

   If we are allowed to appeal to the following facts: $$\sum_{i=1}^{n} i = \frac{n(n+1)}{2} \quad \textrm{and} \quad \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$$ then we can argue the result directly with the following: $$\begin{array}{rcl} \sum_{i=1}^{n} i(i+1) &=& \sum_{i=1}^{n} (i^2 + i)\\\\ &=& \left[ \sum_{i}^{n} i^2 \right] + \left[ \sum_{i}^{n} i \right]\\\\ &=& \left[ \frac{n(n+1)(2n+1)}{6} \right] + \left[ \frac{n(n+1)}{2} \right]\\\\ &=& n(n+1) \left[ \frac{2n+1}{6} + \frac{1}{2} \right] \\\\ &=& n(n+1) \left[ \frac{2n + 4}{6} \right] \\\\ &=& \frac{n(n+1)(n+2)}{3} \end{array}$$ QED.

Part III (Challenge!)

1. Are you curious how someone might have initially figured out the formulas for the various summations in (a)-(d)? Find a formula for $\sum_{i=1}^{n} i^3$ by using the following fact in combination with the results of problems 1-2 in Part I.

   $$\left[ \sum_{i=1}^{n} i^4 \right] + (n+1)^4 = \sum_{i=0}^{n} (i+1)^4$$

    

   The formulas for the sums of powers shown below can all be proven in a straight-forward way with induction -- but each of these proofs requires that one knows what the formula should be ahead of time.

   $$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}, \quad \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}, \quad \sum_{i=1}^{n} i^3 = \frac{n^2(n+1)^2}{4}, \ldots$$

   How then, might one come up with the formulas in the first place?

   The following shows an incredibly clever trick for deducing the formula for $\sum_{i=1}^{n} i^k$ by using all of the related formulas for lesser powers.

   Let us demonstrate the technique through an example...

   Suppose we wish to find the formula for $\sum_{i=1}^{n} i^3$, assuming that we know the following formulas already $$\sum_{i=1}^{n} i = \frac{n(n+1)}{2} \quad \textrm{ and } \quad \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$$ We start by considering the following identity

   $$\left[ \sum_{i=1}^{n} i^4 \right] + (n+1)^4 = \sum_{i=0}^{n} (i+1)^4$$

   Notice, the expression on the right side can be expanded

   $$\begin{array}{rcl} \sum_{i=0}^{n} (i+1)^4 &=& \sum_{i=0}^{n} (i^4 + 4i^3 + 6i^2 + 4i + 1)\\\\ &=& \left[ \sum_{i=0}^{n} i^4 \right] + 4 \left[ \sum_{i=0}^{n} i^3 \right] + 6 \left[ \sum_{i=0}^{n} i^2 \right] + 4 \left[ \sum_{i=0}^{n} i \right] + \left[ \sum_{i=0}^{n} 1 \right]\\\\ \end{array}$$ So, $$\left[ \sum_{i=1}^{n} i^4 \right] + (n+1)^4 = \left[ \sum_{i=0}^{n} i^4 \right] + 4 \left[ \sum_{i=0}^{n} i^3 \right] + 6 \left[ \sum_{i=0}^{n} i^2 \right] + 4 \left[ \sum_{i=0}^{n} i \right] + \left[ \sum_{i=0}^{n} 1 \right]$$ Canceling the sums of the fourth powers on both sides, we arrive at $$(n+1)^4 = 4 \left[ \sum_{i=0}^{n} i^3 \right] + 6 \left[ \sum_{i=0}^{n} i^2 \right] + 4 \left[ \sum_{i=0}^{n} i \right] + \left[ \sum_{i=0}^{n} 1 \right]$$ Substituting the formulas for the sums associated with the lesser powers lets us solve for the remaining sum: $$\begin{array}{rcl} (n+1)^4 &=& 4 \left[ \sum_{i=0}^{n} i^3 \right] + 6 \left[ \frac{n(n+1)(2n+1)}{6} \right] + 4 \left[ \frac{n(n+1)}{2} \right] + (n+1)\\\\ (n+1)^4 &=& 4 \left[ \sum_{i=0}^{n} i^3 \right] + n(n+1)(2n+1) + 2n(n+1) + (n+1)\\\\ \end{array}$$ Isolating the summation on the left side, we have $$\begin{array}{rcl} \sum_{i=0}^{n} i^3 &=& \displaystyle{\frac{(n+1)^4 - n(n+1)(2n+1) - 2n(n+1) - (n+1)}{4}}\\\\ &=& \displaystyle{\frac{(n+1)[(n+1)^3 - n(2n+1) - 2n - 1]}{4}}\\\\ &=& \displaystyle{\frac{(n+1)(n^3 + 3n^2 + 3n + 1 - 2n^2 - n - 2n - 1)}{4}}\\\\ &=& \displaystyle{\frac{(n+1)(n^3 + n^2)}{4}}\\\\ &=& \displaystyle{\frac{n^2(n+1)^2}{4}} \end{array}$$ This yields the formula we sought to acquire: $$\sum_{i=0}^{n} i^3 = \frac{n^2(n+1)^2}{4}$$ Isn't that just a delightfully beautiful trick!

2. 🔎 Find $\sum_{i=1}^{n} i^4$ in a manner similar to how $\sum_{i=1}^{n} i^3$ was found above.