Mathematical induction also works for a sequence Pk Pk 1 o

Mathematical induction also works for a sequence P_k, P_k + 1, ... of propositions, indexed by the integers n greaterthanorequalto k for some k N. The statement is: if P_k is true and P_n + 1 is true whenever P_n is true and n greaterthanorequalto k, then P_n is true for all n greaterthanorequalto k. Prove this. Use induction in the form stated in the preceding exercise to prove that n^2

Solution

Check for n = 5

=> 5² < 2⁵

=> 25 < 32

Hence , the condition n² < 2ⁿ is true for n = 5

Let the result be true for n = k

=> k² < 2^k

To Prove : (k + 1)² < 2^k+1

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

=> (k + 1)² < 2^k + 2k + 1 < 2^k + k² ( As 2k + 1 < k² for k > 3 )

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

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