Problem 2 Use mathematical induction to prove If n is a nonn

Problem 2: Use mathematical induction to prove:

If n is a nonnegative integer, then 2ⁿ > n

Use the following steps:

(i) prove that P(0) is true.

(ii) Suppose k>=0. Prove that P(k) is true implies P(k+1) is true.

Suppose P(k) is true, write down P(k) here:

Write down P(k+1) here:

Assuming that P(k) is true, show P(k+1) is true:
Hint: start with:

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

Be sure to use that P(k) is true

we have to prove p(n) = 2ⁿ > n

p(0) = 2⁰ >0 = 1 > 0

p(1) = 2¹ >1 = 2 >1

since p(0) is true and p(1) is also true

therefore p(k) is true

p(k) = 2^k > k.................eqn.{1}

and we have to prove that p(k+1) is true

multiplying both sides by 2 in eqn 1

p(k) = 2 x 2^k > 2k

p(k) = 2^k+1 > k+k

p(k) = 2^k+1 > k+1 .....................{ k>1 }

p(k) can be written as p(k+1)

p(k+1) = 2^k+1 > k+k

we have proved p(k+1) is true

therefore it is true for all values of k