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

  • Thread starter Thread starter leo255
  • Start date Start date
  • Tags Tags
    Induction
AI Thread Summary
The discussion revolves around proving the inequality 2^n >= 11n + 17 for integers n >= 7 using mathematical induction. The initial step verifies the base case for n=7, confirming that 128 >= 94 is true. The induction hypothesis assumes that 2^k >= 11k + 17 holds for some integer k, and the goal is to prove it for k+1. Participants suggest refining the proof by starting with the left side of the inequality and emphasize the importance of proper notation, particularly using parentheses in exponents. The conversation highlights the need for clarity and correctness in mathematical arguments while progressing through the proof.
leo255
Messages
57
Reaction score
2

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.
 
Physics news on Phys.org
leo255 said:
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.
 
  • Like
Likes 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
 
leo255 said:
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

2k+1≥22k+34

Just continue with the right hand side...
 
  • Like
Likes leo255
Yes, you have the correct argument. I will suggest ways to write it up nicer.

leo255 said:

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.
 
Last edited:
  • Like
Likes leo255
Very helpful, thanks guys!
 
leo255 said:

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!
 
Ray Vickson said:
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##
 
Back
Top