Use mathematical induction to prove the truth of the followi

Use mathematical induction to prove the truth of the following:

2n + 1 ? 2ⁿ for n ? 3

Use mathematical induction to prove the truth of the following:

1 + 2 + 4 + ... + 2ⁿ = 2^{n + 1}

Solution

Use mathematical induction to prove the truth of the following:

2n + 1 ? 2^n for n ? 3

Step 1 : Check for n = 3

2(3) + 1 <= 2^3
7 <= 8
TRUE

Step 2 : Assume it is true for n = k....

2k + 1 <= 2^k

Step 3 : Prove that it is true for n = k + 1.....

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

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

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

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

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

Now, for k >= 3, we know that 2(2^k - 1) is definitely greater than 2^k

Hence proved that :

2k + 1 <= 2(2^k -1) is ALWAYS TRUE

Hence by principles of induction, the statement has been proved!
-----------------------------------------------------------------------------

1 + 2 + .. 2^n = 2^(n+1) - 1

Step 1 : Prove that it is true for n = 0....

2^0 = 2^(0+1) - 1
1 = 2^1 - 1
1 = 2 - 1
1 = 1
TRUE

Step 2 : Assume tis true for n = k/...

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

Step 3 : Prove that it is true for n = k+1....

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

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

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

2^(k+1+1) - 1

2^(k+2) - 1 = RIGHT HAND SIDE

Hence proved!