What do you show in the basis step and what do you show in the inductive step when you use (ordinary) mathematical induction to prove that a property involving an integer n is true for all integers greater than or equal to some initial integer?

• Basis step
• Show that p(n) is true
• Inductive step
• Show that any integer k greater or equal n0, if P(k) is true, then P(k+1) is true

Example

• Prove that for any natural number n,   0 + 1 + ... + n = n( n + 1 )/2
• Basis step:
• If n = 0, then LHS = 0, RHS = 0 * (0+1) = 0
• LHS (0) = RHS (0)

• Inductive step:
• LHS à n + 1 = 0 + 1 + … + n + (n + 1) = (0 + 1 + … + n) + (n + 1)
• n(n + 1)/2 + (n + 1) – using induction hypothesis
• (n + 1)(n + 2)/2 – factoring (n + 1)
• LHS = RHS for n + 1

What is the inductive hypothesis in a proof by (ordinary) mathematical induction?

• Inductive hypothesis is the assumption in inductive step that statement hold for some n.

• In order to perform the inductive step, one must assumes the inductive hypothesis and then uses this assumption to prove the statement for n + 1.

• Inductive hypothesis indicates in three ways:
• by explicit mention in the text
• by inserting acronym IH over an equal sign or a sign for an inequality
• by specify the inductive hypothesis as the reason for a step in a multi-line display

Use (ordinary) mathematical induction to construct proofs involving various kinds of statements such as formulas, divisibility properties and inequalities

Formulas:

Show that if n is a positive integer,

1 + 2+…..+n  =  n(n+1)
                                2

Solution:

Let P(n) be the proposition that the sum of the first n positive integers, 1+2+…+n=n(n+1)/2. We must do two things to prove that P(n) is true for n = 1, 2, 3, . . .

Show that P(1) is true and that the conditional statement P(k) implies P(k + 1) is true for k = 1, 2, 3,…..

BASIS STEP:

P(1) is true, because 1 =  1(1+1)
                                                 2

INDUCTIVE STEP:

1 + 2+· · ·+k =  k(k+1)
                               2

Show that P(k + 1) is true,

1 + 2+· · ·+k + (k + 1) = (k+1)[(k+1)+1]
                                                    2
                                         
                                     = (k+1)(k+2)
                                                2

Add k + 1 to both sides of the equation in P(k),

1+2+....+k+(k + 1)= k(k+1)
                                   2       +(k+1)
                            

                            = k(k+1)+2(k+1)
                                         2
                            = (k+2)(k+1)
                                       2

This last equation shows that P(k + 1) is true under the assumption that P(k) is true. This completes the inductive step. We have completed the basis step and the inductive step, so by mathematical induction we know that P(n) is true for all positive integers n.

 1 + 2+· · ·+n =n(n + 1)/2 for all positive integers n have proven.

Divisibility properties

Proposition:

For any integer n≥1, 7ⁿ - 2ⁿ is divisible by 5.        

Proof :

1) Basis step:

The statement is true for n=1:                                                      

                                   7¹ – 2¹ = 7 - 2 = 5 is divisible by 5.

2) Inductive step:

Assume the statement is true for some k≥1                              

                                                            (inductive hypothesis) ;

P(k):                7^k - 2^k is divisible by 5.                                                 

            Then 7^k - 2^k = 5a   for some aÎZ .                                

 We need to show:

P(k+1):7^k+1 - 2^k+1 is divisible by 5.                                                                

             7^k+1 - 2^k+1 = 7·7^k - 2·2^k = 5·7^k + 2·7^k - 2·2^k

                                    = 5·7^k + 2·(7^k - 2^k)  =  5·7^k + 2·5a           

                                    = 5·(7^k + 2a) which is divisible by 5.                         

Show that it is true for k+1.                                                     

P(n) is true by induction.   

Inequalities

Theorem:

 For all integers n≥5,    n² < 2ⁿ.                         

Proof (by induction):

1) Basis step:

                        The statement is true for n=5:                             

                                                            5² =25 < 32 = 2⁵.

2)Inductive step:

Assume the statement is true for some k≥5 ;                        

P(k):                          k² < 2^k.                                              

We need to show:  

P(k+1):                 (k+1)² < 2^k+1.                                                              

             (k+1)² = k²+2k+1 < k² +2^k                

                                           < 2^k + 2^k                        

                                           = 2·2^k  = 2^k+1.

                                   

Show that it is true for k+1 .                                          

Thus, P(n) is true by induction.