Transcript 7 : Induction

Induction
• Induction is basically a method for proving
theorems about the natural numbers.
• The method is important in computing
applications; it is closely related to recursion,
and it is a useful tool if you are trying to
establish that an algorithm is correct.
• A proof by induction on nature numbers of a
given statement (or formula) consists of two
steps:
• 1- ( base step) Prove that the statement is true
when n=1 .
• 2- ( Inductive step) Prove that if the statement
is true for any particular value k , then it is also
true for the next value of n=k+1 .
Example (1) Prove by induction:
1  2  3  ...  n 
n (n  1)
2
• Proof:
• Base step: Let put n  1 , then 1  1(12 1) is true.
• Inductive step: assume that the formula is true
for a fixed arbitrary natural number k :that is
1  2  3  ...  k 
k (k  1)
2
• (This assumption is called the inductive
hypothesis)
• We need to deduce from this assumption that
the formula is also true when n  k  1.
The left-hand side of the formula is
1  2  3  ...  k  (k  1)
Then by using the inductive hypothesis we get
1  2  3  ...  k  ( k  1) 
k (k  1)
 k 1
2
k
 1)
2
(k  1)(k  2)

2
(k  1)  ( k  1)  1

2
 (k  1)(
The last line is with k+1 in place of n.
So, the formula is also true for k+1.
n ( n  1)
1  2  3  ...  n 
Thus by induction,
2
for all natural numbers.
Example (2)
Prove by induction the following statement
2  22  23  ...  2n  2n 1  2
Proof:
11
2

2
 2 is true.
Base step : Let n = 1. Then:
Inductive step: now, assume, for n = k, the statement is held; that is,
2  22  23  ...  2k  2k 1  2
We need to show that for n = k + 1, the formula is also true.
2  22  23  ...  2k  2k 1  2k 1  2  2k 1
 2.2k 1  2
 2( k 1)1  2
.
So the formula is true for n = k + 1
Example 3 : For any natural number n ,
n3 + 2n is divisible by 3.
• Proof:
Basis Step: If n = 1, then n3 + 2n = 13 + 2(1) = 3. So it is
divisible by 3.
• Inductive step: Assume that for an arbitrary natural number k,
k3 + 2k is divisible by 3.
• To prove this for k+1,
( k + 1 )3 + 2( k + 1 ) = ( k3 + 3k2 + 3k+ 1 ) + ( 2k+ 2 )
= ( k3 + 2k ) + ( 3k2 + 3k+ 3 )
= ( k3 + 2k ) + 3( k2 + k + 1 )
• which is divisible by 3, because ( k3 + 2k ) is divisible by 3
(by assumption) and 3( k2 + k + 1 ) is also divisible by 3. So,
by the induction the given statement is true for all n.
Example (4) Prove that
8n – 3n is divisible by 5.
Proof
• Base step : Let n = 1.
Then the expression 8n – 3n evaluates to 81 – 31 = 5, which is clearly
divisible by 5.
• Inductive step: assume, for n = k, then 8k – 3k is divisible by 5.
Let n = k + 1.
Then:
8k+1 – 3k+1 = 8k+1 – 3×8k + 3×8k – 3k+1
= 8k(8 – 3) + 3(8k – 3k)
= 8k(5) + 3(8k – 3k)
• The first term 8k(5) is divisible by 5 and
3(8k – 3k) is also divisible by 5 (by
assumption). then the entire expression,
8k(5) + 3(8k – 3k) = 8k+1 – 3k+1, must be
divisible by 5.
• Then, for n = k + 1, the statement holds.
Thus for all n.
Example (5) Prove that
5n – 1 is divisible by 4.
Proof
• Base step : Let n = 1.
Then the expression 5n – 1 evaluates to 51 – 1 = 4, which is
clearly divisible by 4.
•
Inductive step: assume, for n = k, then 5k – 1 is divisible
by 4.
5k – 1 = q
4
Then 5k – 1 = 4q
= 4q + 1
or
Let n = k + 1.
5k+1 – 1 = (5k 5) –1
= [(4q +1) 5] – 1
= 5 4q + 5-1