Induction

Use of Mathematical Induction



Subjects to be Learned

Contents

Sometimes when you see a recurring pattern in the value of some mathematical expression, such as the sum of some terms, you may be able to guess a general formula for the value. To verify or disprove your guess, you may be able to use mathematical induction. An example is given below.

We have seen that for any natural number n
1 + 2 + ... + n = n( n + 1 )/2
and
12 + 22 + ... + n2 = n( n + 1 )( 2n + 1 )/6
hold.

One might then wonder what 13 + 23 + ... + n3 would be equal to.
One way to find that out is to make a conjecture (i.e. educated guess) and prove the conjecture.

Let us first take a guess.
By looking at the sums 1 + 2 + ... + n = n( n + 1 )/2 --- a function of n2
and 12 + 22 + ... + n2 = n( n + 1 )( 2n + 1 )/6 --- a function of n3 ,
one can guess that 13 + 23 + ... + n3 is equal to some function of n4, that is
13 + 23 + ... + n3 = an4 + bn3 + cn2 + dn + e ---- (1) for some constants a, b, c, d and e.

Now to determine the value of a, b, c, d and e, we compare the value of the both sides of the equation (1) for five values of n.
For n = 0, LHS = 0, and RHS = e. Hence we get e = 0.
Similarly for n = 1, 1 = a + b + c + d,
for n = 2, 9 = 16a + 8b + 4c + 2d,
for n = 3, 36 = 81a + 27b + 9c + 3d , and
for n = 4, 100 = 256a + 64b + 16c + 4d .

Solving this system of equations we obtain
a = c = 1/4, b = 1/2, and d = 0.
Hence our conjecture is
13 + 23 + ... + n3 = 1/4 n2 ( n2 + 2n + 1 ) = ( 1/2 n ( n + 1 ) )2 .

What we do next is to try to prove it by mathematical induction.

Proof by Mathematical Induction:
Basis Step: For n = 0, LHS = 03 = 0 , and
RHS = ( 1/2* 0 ( 0 + 1 ) )2 = 0 .
Hence LHS = RHS.
Induction: Assume that 13 + 23 + ... + n3 = ( 1/2 n ( n + 1 ) )2  for an arbitrary n. --------- Induction Hypothesis
Then for n + 1, LHS = 13 + 23 + ... + n3 + ( n + 1 )3
    = (13 + 23 + ... + n3) + ( n + 1 )3
    = ( 1/2 n ( n + 1 ) )2 + ( n + 1 )3   by the induction hypothesis.
    = ( 1/4 ( n + 1 )2( n2 + 4*( n + 1 ) )
    = ( 1/2 ( n + 1 )( n + 2 ) )2 ,
which is equal to RHS.
End of Proof

Thus we now know for sure that
13 + 23 + ... + n3 = ( 1/2 n ( n + 1 ) )2 .


Next -- Program Correctness using Induction
Next -- Second Principle of Mathematical Induction

Back to Schedule
Back to Table of Contents