2

Making a proof

for $n>7$

$$2^n>n^2+4n+5$$

Step 1

For $$n=7$$

$$2^7=128>7^2+4(7)+5=82$$

It is TRUE for $n=7$

Step 2

Inductive Hypotesis: It must be true for $n=k$

$$2^k>k^2+4k+5$$

Step 3

3.1:

$$2^{k+1}>(k+1)^2+4(k+1)+5$$

But, after this it was said that...

It is needed to multiply by $2$ the expression in the induction step 2

3.2:

$$2^{k+1}>2k^2+8k+10$$

Make some transformation (that also do not understand):

3.3:

$$2^{k+1}>(k+1)^2+4(k+1)+5+k^2+2k$$

Making with that the proof by understanding that $k^2+2k>0$ for any $k\ge7$ We can deduce that $2^{k+1}>(k+1)^2+4(k+1)+5$

Questions

a: It is right to go from 2 to 3.1? In which way?

b: How we go from 3.1 to 3.2?

c: How we go from 3.2 to 3.3?

Source: http://esaez.mat.utfsm.cl/iii.pdf, August, 2013, pp.2

Haizum Skallah
  • 653

2 Answers2

2

We want to show $2^n > n^2 + 4n + 5$ for all $7 \leq n \in \mathbb{N}$. First of all, we want to show that, this is true for $7$. Then, we will assume this is true for $n$ and try to show for $n+1$. So, step $2$ is assumption and $3.1$ is what we want to show. You wrote $3.2$ wrongly (with edits, it's now correct), but yes we will use our assumption and look what will happen when we multiply it by $2$. We get: $$2^{k+1} > 2k^2 + 8k + 10$$ Then, observe that $$(k+1)^2 + 4(k+1) + 5 + k^2 + 2k = 2k^2 + 8k + 10$$ Remember, we want to show that $2^{k+1} > (k+1)^2 + 4(k+1) + 5$. Also, $k^2+2k > 0$ . Try to finish this and if you can't please comment.

aeyalcinoglu
  • 534
1

a. Your goal is to go from 2 to 3.1; that will complete the induction.

b,c. You do not go from 3.1 to anywhere, you end up at 3.1.

Here is how to go from 2 to 3.1:
Method 1: Multiply both sides of step 2 by $2^1$. This will make the LHS agree with 3.1. Then you will need to prove that $2(k^2+4k+5) > (k+1)^2+4(k+1)+5$, to make the RHS agree.

Method 2: Add a polynomial in $k$ to both sides of step 2, to make the RHS agree with 3.1. The correct polynomial is $(k+1)^2+4(k+1)+5-(k^2+4k+5)=2k+5$. Then you will need to prove that $2^{k+1}>2^k+(2k+5)$, to make the LHS agree.

vadim123
  • 82,796