topic badge
India
Class XI

Inductive Proofs for Sums of Integers

Lesson

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}$AkAk+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}$AkAk+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+...+(4n1)=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+...+(4k1)=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+...+(4k1)+[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+...+(4k1)+(4k+3)=[(k+1)(2k+3)]

Then:

$LHS$LHS $=$= $3+7+11+...+\left(4k-1\right)+\left(4k+3\right)$3+7+11+...+(4k1)+(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}$AkAk+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.

  1. Write the equation when $n=4$n=4.

    Do not simplify each side.

    $\editable{}$

  2. Evaluate the left hand side of the equation.

  3. Evaluate the right hand side of the equation.

  4. Is the equation true or false when $n=4$n=4?

    False

    A

    True

    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)
  1. 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.

  2. 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.

  3. 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=.

  4. 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.

  5. Now substitute $n=k+1$n=k+1 into the right hand side of the identity and simplify, leaving your answer in factorised form.

  6. 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

  1. 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.

  2. 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.

  3. 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=.

  4. 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.

  5. Now substitute $n=k+1$n=k+1 into the right hand side of the identity and simplify, leaving your answer in factorised form.

  6. 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.

Outcomes

11.A.PMI.1

Processes of the proof by induction, motivating the application of the method by looking at natural numbers as the least inductive subset of real numbers. The principle of mathematical induction and simple applications.

What is Mathspace

About Mathspace