hi,

can anyone explain these steps to me? im abit lost? especially step 2 and 3

Exercise 4(c) To prove that 3^n > n^2, i.e., 3^n − n^2 > 0, using proof

by induction, we first check it for n = 1: i.e., 3^1 = 3 > 1^2 = 1 . X

Inductive step: now assume it is true for n = k, i.e.,

solution

assume that

3k − k^2 > 0. For n = k + 1

3^k+1 − (k + 1)^2 = 3 × 3^k − (k + 1)^2

= 3(3^k − k^2 + k^2) − (k + 1)^2 [2]

= 3(3^k − k^2) + 3k^2 − k2 − 2k − 1 [3]

= 3(3^k − k^2) + k^2 + k^2 − 2k − 1

= 3(3^k − k^2) + k^2 + (k − 1)2 − 2