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

[leo255]

Homework Statement

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

Homework Equations

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.

 

[Svein]

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

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

 

[leo255]

Thanks for the reply,

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

 

[Svein]

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

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

2^k+1≥22k+34

Just continue with the right hand side...

 

[LCKurtz]

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

Homework Statement

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

Homework Equations

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 = 11k + 28

You need parentheses in the exponents here and below.

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

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.

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.

 

[leo255]

Very helpful, thanks guys!

 

[Ray Vickson]

Homework Statement

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

Homework Equations

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.

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!

 

[Mark44]

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!

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