Question

Please be able to follow the COMMENT

Use induction proof to prove that For all positive integers n we have the inequality n<=2^n

here is the step: base step: P(1)= 1<=2^1    inductive step: k+1<= 2^(k)+1 <= 2^(k)+k (since k>=1) <= 2^(k)+2^(k) = 2X2^(k) =2^(k+1)

i don't understand why 1 can be replaced by k and i don't know why since k>=1

Answer 1

QuestioN;

Use Induction Proof to provethat for all positive integers, we have the inequality:

n 2ⁿ                         (1)

Proof:

Step 1:

Base step:

For n = 1, putting in (1), w get:

1 2¹

i.e.,

1 2

Thus, the result is true for n =1

Step 2:

Inductive step :

Assume the result is true for k.

i.e.,

Let

is true.

Step 3:

Based on Step 2, to prove it is true for k + 1.

i.e.,

To prove:

                  (2)

Step 4:

Since by (1):

,

Adding 1 to both sides, we get:

            (3)

Since k1, we can replace 1 by k on RHS without affecting the result.

EXPLANATION:

(3) is an inequality. k is greater than or equal to 1. So, we can replace 1 by k on RHS without affecting the result.

Thus, we get:

           (4)

Step 5:

By similar argument, since k is greater than or equal to 1, we can replace k by 2^k on RHS without affecting the result.

Thus, we get:

i.e.,

i.e.,

This is the required result.