Prove by induction: 2^n >= 11n + 17

1. Dec 14, 2015

leo255

1. The problem statement, all variables and given/known data

Prove by mathematical induction: 2^n >= 11n + 17, for n >= 7, and n is an integer.

2. Relevant equations

3. The attempt at a solution

This is my attempt - I want to see if I'm doing this correctly.

2^n >= 11n + 17, n >= 7

basis 2^7 >= 77 + 17

128 >= 94. True.

Induction Hypothesis:
Assume true:
2^k >= 11k + 17

Must prove:
2^k+1 >= 11(k+1) + 17

2^k * 2 >= 2*(11k + 17) <-- By induction hypothesis, just multiplying both sides by 2.
2^k * 2 >= 22k + 34

2^k*2 >= 11(k + 1) + 17
2^k*2 >= 11k + 28

2^k+1 >= 11k+28, because
2^k+1 >= 22k + 34, and 11k + 28 will always be a smaller number.

2. Dec 14, 2015

Svein

Correct up to this point, but then I do not see what you are up to.

3. Dec 14, 2015

leo255

I was just expanding out the k+1, so I could say definitively that the expression being multiplied by 2 in the hypothesis is larger 11(k + 1) + 17

4. Dec 14, 2015

Svein

It seems to me that you are trying to run the proof backwards at this point. You have shown that

2k+1≥22k+34

Just continue with the right hand side...

5. Dec 14, 2015

LCKurtz

Yes, you have the correct argument. I will suggest ways to write it up nicer.

You need parentheses in the exponents here and below.

Above, it would be better to start with the left side of what you are to prove$$2^{k+1} = 2\cdot 2^k \ge 2(11k+17) = 22k+34 > 11k+28$$which is much more succinct than what you have below.

Last edited: Dec 14, 2015
6. Dec 14, 2015

leo255

7. Dec 14, 2015

Ray Vickson

You wrote $2^k + 1 \geq 11(k+1) + 17$. I assume you mean $2{k+1} \geq 11(k+1) + 17$, and if so you need to use parentheses, like this: 2^(k+1) >= 11(k+1) + 17. So simple, yet so crucial!

8. Dec 14, 2015

Staff: Mentor

In the part, "I assume you mean...", what you really meant was $2^{k+1} \geq 11(k+1) + 17$