Induction
Use of Mathematical Induction
Subjects to be Learned
- guessing and verifying using induction
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