Inductive Proofs for Sums of Integers
We now demonstrate how mathematical induction can be used to establish formulae for certain sums to $n$n terms.
Example 1
Establish the following result by mathematical induction:
$1+2+3+.....+n=\frac{n\left(n+1\right)}{2}$1+2+3+.....+n=n(n+1)2
This famous formula for the sum of the positive integers can be proved in a number of ways, but this is a good place to start with induction.
As an assertion $A_n:$An: $1+2+3+.....+n=\frac{n\left(n+1\right)}{2}$1+2+3+.....+n=n(n+1)2
Check $A_1$A1:
Here, for $n=1$n=1 we have $\frac{1\left(1+1\right)}{2}=1$1(1+1)2=1 and so true for $n=1$n=1
We could check $A_2$A2 and perhaps $A_3$A3, but all we really need is one case to be verified
To prove the conditional $A_k\Rightarrow A_{k+1}$Ak⇒Ak+1
First assume $A_k$Ak: $1+2+3+.....+k=\frac{k\left(k+1\right)}{2}$1+2+3+.....+k=k(k+1)2
Then use $A_k$Ak to prove $A_{k+1}$Ak+1:
$A_{k+1}$Ak+1: $1+2+3+.....+k+\left(k+1\right)=\left[\frac{\left(k+1\right)\left(k+2\right)}{2}\right]$1+2+3+.....+k+(k+1)=[(k+1)(k+2)2]
(Make sure you check this line. The number $k+1$k+1 has been added to the left hand side, and the right hand side reflects the same formula as $A_k$Ak with $k$k being replaced by $k+1$k+1 wherever it occurs)
We need to prove that the left hand side equals the right hand side. Use the assumption to replace the expression $1+2+3+...+k$1+2+3+...+k with $\frac{k\left(k+1\right)}{2}$k(k+1)2.
Thus:
| $LHS$LHS | $=$= | $1+2+3+.....+k+\left(k+1\right)$1+2+3+.....+k+(k+1) |
| $=$= | $\frac{k\left(k+1\right)}{2}+\left(k+1\right)$k(k+1)2+(k+1) | |
| $=$= | $\frac{k\left(k+1\right)}{2}+\frac{2\left(k+1\right)}{2}$k(k+1)2+2(k+1)2 | |
| $=$= | $\frac{\left(k+1\right)}{2}\left[k+2\right]$(k+1)2[k+2] | |
| $=$= | $\frac{\left(k+1\right)\left(k+2\right)}{2}$(k+1)(k+2)2 | |
| $=$= | $RHS$RHS |
Therefore $A_k\Rightarrow A_{k+1}$Ak⇒Ak+1 has been established. We use the conditional to prove for all $n$n.
Since $A_1$A1 was originally established, then so also is $A_2$A2, and because $A_2$A2 is established, so also is $A_3$A3. Continuing in this manner, we see that it is true for all $n$n.
Here is a nice diagram to visualise the concept of an induction proof:
Once you understand the concept, the procedure and the working can be greatly simplified.
In the next example, we will see how mathematicians usually write an induction proof.
Example 2
Prove the summation formula given by $3+7+11+...+\left(4n-1\right)=n\left(2n+1\right)$3+7+11+...+(4n−1)=n(2n+1).
Check $A_1$A1 $n=1:$n=1: $1\left(2\times1+1\right)=3$1(2×1+1)=3 True!
Assume $A_k$Ak $3+7+11+...+\left(4k-1\right)=k\left(2k+1\right)$3+7+11+...+(4k−1)=k(2k+1)
To prove $A_{k+1}:$Ak+1:
$3+7+11+...+\left(4k-1\right)+\left[4\left(k+1\right)-1\right]=\left[\left(k+1\right)\left(2\left(k+1\right)+1\right)\right]$3+7+11+...+(4k−1)+[4(k+1)−1]=[(k+1)(2(k+1)+1)]
or, more simply...
$3+7+11+...+\left(4k-1\right)+\left(4k+3\right)=\left[\left(k+1\right)\left(2k+3\right)\right]$3+7+11+...+(4k−1)+(4k+3)=[(k+1)(2k+3)]
Then:
| $LHS$LHS | $=$= | $3+7+11+...+\left(4k-1\right)+\left(4k+3\right)$3+7+11+...+(4k−1)+(4k+3) |
| $=$= | $k\left(2k+1\right)+\left(4k+3\right)$k(2k+1)+(4k+3) | |
| $=$= | $2k^2+5k+3$2k2+5k+3 | |
| $=$= | $\left(k+1\right)\left(2k+3\right)$(k+1)(2k+3) | |
| $=$= | $RHS$RHS | |
Since it is true for $n=1$n=1, from $A_k\Rightarrow A_{k+1}$Ak⇒Ak+1, it is also true for $n=2$n=2, and in turn for $n=3$n=3 etc. Therefore it is true for all $n$n.
Example 3
In our final example we'll see how sometimes the algebra can become a little more complex. The same basic ideas apply though.
Prove that $1\times2+2\times3+3\times4+....+n\left(n+1\right)=\frac{1}{3}n\left(n+1\right)\left(n+2\right)$1×2+2×3+3×4+....+n(n+1)=13n(n+1)(n+2)
When $n=1$n=1, we have $1\times2=2$1×2=2 and this equals $\frac{1}{3}\times1\left(1+1\right)\left(1+2\right)$13×1(1+1)(1+2).
Assume $A_k$Ak $1\times2+2\times3+3\times4+....+k\left(k+1\right)=\frac{1}{3}k\left(k+1\right)\left(k+2\right)$1×2+2×3+3×4+....+k(k+1)=13k(k+1)(k+2)
To prove $A_{k+1}:$Ak+1:
$1\times2+2\times3+3\times4+....+k\left(k+1\right)+\left(k+1\right)\left(k+2\right)=\frac{1}{3}\left(k+1\right)\left(k+2\right)\left(k+3\right)$1×2+2×3+3×4+....+k(k+1)+(k+1)(k+2)=13(k+1)(k+2)(k+3)
Thus:
| $LHS$LHS | $=$= | $1\times2+2\times3+3\times4+....+k\left(k+1\right)+\left(k+1\right)\left(k+2\right)$1×2+2×3+3×4+....+k(k+1)+(k+1)(k+2) |
| $=$= | $\frac{1}{3}k\left(k+1\right)\left(k+2\right)+\left(k+1\right)\left(k+2\right)$13k(k+1)(k+2)+(k+1)(k+2) | |
| $=$= | $\frac{1}{3}\left[k\left(k+1\right)\left(k+2\right)+3\left(k+1\right)\left(k+2\right)\right]$13[k(k+1)(k+2)+3(k+1)(k+2)] | |
| $=$= | $\frac{1}{3}\left(k+1\right)\left[\left(k+2\right)\left(k+3\right)\right]$13(k+1)[(k+2)(k+3)] | |
| $=$= | $\frac{1}{3}\left(k+1\right)\left(k+2\right)\left(k+3\right)$13(k+1)(k+2)(k+3) | |
| $=$= | $RHS$RHS |
Hence if its true for $n=k$n=k, then its true for $n=k+1$n=k+1, and since it is true for $n=1$n=1, it is true for all $n$n.
Worked Examples
Question 1
We want to find out if the equation $1^2+2^2+3^2+\dots+n^2=\frac{n\left(n+1\right)\left(2n+1\right)}{6}$12+22+32+…+n2=n(n+1)(2n+1)6 holds when $n=4$n=4.
Write the equation when $n=4$n=4.
Do not simplify each side.
$\editable{}$
Evaluate the left hand side of the equation.
Evaluate the right hand side of the equation.
Is the equation true or false when $n=4$n=4?
False
ATrue
B
Question 2
We want to use mathematical induction to prove, for all positive integers $n$n, that:
| $1^2+2^2+3^2+\dots+n^2$12+22+32+…+n2 | $=$= | $\frac{n\left(n+1\right)\left(2n+1\right)}{6}$n(n+1)(2n+1)6 |
| ($LHS$LHS) | ($RHS$RHS) |
We will begin by proving the initial case, when $n=1$n=1.
Start by evaluating the left hand side $1^2+2^2+3^2+\dots+n^2$12+22+32+…+n2 when $n=1$n=1.
Now evaluate the right hand side $\frac{n\left(n+1\right)\left(2n+1\right)}{6}$n(n+1)(2n+1)6 when $n=1$n=1 to show that they are equal. Make sure to show all working.
To continue our proof by induction, we now assume that the identity is true for $n=k$n=k.
That is, we assume $1^2+2^2+3^2+\dots+$12+22+32+…+$\left(\editable{}\right)^2$()2$=$=$\frac{\left(\editable{}\right)\left(\editable{}\right)\left(\editable{}\right)}{\editable{}}$()()().
We then aim to use this assumption to prove that the identity is true for $n=\editable{}$n=.
When $n=k+1$n=k+1, the left hand side of the identity takes the form $1^2+2^2+3^2+\ldots+k^2+\left(k+1\right)^2$12+22+32+…+k2+(k+1)2.
Use the equation assumed in part (c) to rewrite this expression as a single fraction. Simplify your answer, leaving it in factorised form.
Now substitute $n=k+1$n=k+1 into the right hand side of the identity and simplify, leaving your answer in factorised form.
From parts (a) and (b) we know that $1^2+2^2+3^2+\dots+n^2=\frac{n\left(n+1\right)\left(2n+1\right)}{6}$12+22+32+…+n2=n(n+1)(2n+1)6 is true for $n=\editable{}$n=.
From parts (c) to (e) we know that if $1^2+2^2+3^2+\dots+n^2=\frac{n\left(n+1\right)\left(2n+1\right)}{6}$12+22+32+…+n2=n(n+1)(2n+1)6 is true for $n=\editable{}$n= then it is true for $n=\editable{}$n=.
Therefore, by induction, $1^2+2^2+3^2+\dots+n^2=\frac{n\left(n+1\right)\left(2n+1\right)}{6}$12+22+32+…+n2=n(n+1)(2n+1)6 is true for all positive integers $n$n.
Question 3
Use mathematical induction to prove, for all positive integers $n$n, that:
$1^3+2^3+3^3+\text{. . .}+n^3=\frac{n^2\left(n+1\right)^2}{4}$13+23+33+. . .+n3=n2(n+1)24
We will begin by proving the initial case, when $n=1$n=1.
Start by evaluating the left hand side $1^3+2^3+3^3+\text{. . .}+n^3$13+23+33+. . .+n3 when $n=1$n=1.
Now evaluate the right hand side $\frac{n^2\left(n+1\right)^2}{4}$n2(n+1)24 when $n=1$n=1 to show that they are equal. Make sure to show all working.
To continue our proof by induction, we now assume that the identity is true for $n=k$n=k.
That is, we assume $1^3+2^3+3^3+\dots+$13+23+33+…+$\left(\editable{}\right)^3$()3$=$=$\frac{\left(\editable{}\right)^2\left(\editable{}\right)^2}{\editable{}}$()2()2.
We then aim to use this assumption to prove that the identity is true for $n=\editable{}$n=.
When $n=k+1$n=k+1, the left hand side of the identity takes the form $1^3+2^3+3^3+\ldots+k^3+\left(k+1\right)^3$13+23+33+…+k3+(k+1)3.
Use the equation assumed in part (c) to rewrite this expression as a single fraction. Simplify your answer, leaving it in factorised form.
Now substitute $n=k+1$n=k+1 into the right hand side of the identity and simplify, leaving your answer in factorised form.
From parts (a) and (b) we know that $1^3+2^3+3^3+\text{. . .}+n^3=\frac{n^2\left(n+1\right)^2}{4}$13+23+33+. . .+n3=n2(n+1)24 is true for $n=\editable{}$n=.
From parts (c) to (e) we know that if $1^3+2^3+3^3+\text{. . .}+n^3=\frac{n^2\left(n+1\right)^2}{4}$13+23+33+. . .+n3=n2(n+1)24 is true for $n=\editable{}$n= then it is true for $n=\editable{}$n=.
Therefore, by induction, $1^3+2^3+3^3+\text{. . .}+n^3=\frac{n^2\left(n+1\right)^2}{4}$13+23+33+. . .+n3=n2(n+1)24 is true for all positive integers $n$n.