Simple proof of inequality by induction

In summary, the goal is to prove that 2n+1<2^n for n=3,4,... The base case holds and it is assumed to be true for P(k). By adding 2 to both sides and multiplying the RHS by 2, it is shown that the inequality still holds for P(k+1). It is then proven that 2^k+2<2^k \cdot 2 for k>1, which completes the proof.
  • #1
naele
202
1

Homework Statement


Prove [tex]2n+1< 2^n[/tex] for n=3,4,...

Homework Equations


The Attempt at a Solution


[tex]
P(3)= 6+1<2^3
[/tex]
The base case holds, now assume true for [itex]P(k)[/itex]. Now consider [itex]P(k+1)[/itex]
[tex]
2(k+1) +1 = 2k+3 [/tex]
[tex]
2^{k+1} = 2^k \cdot 2
[/tex]

So this is where I get stuck, I don't quite know how to finish the proof. As can be seen, the difference between the two sides of the inequality in P(k+1) is that the LHS has 2 added, while the RHS is multiplied by 2. Would it be sufficient to observe that in the base case, adding 2 to the LHS and multiplying the RHS by 2 still maintains the inequality and so necessarily it should hold for any larger n?
 
Physics news on Phys.org
  • #2
2(k+1) +1 = 2k+3 = (2k+1) + 1
2^{k+1} = 2.2^k

so starting with the case for n
2n+1<2n

add 2 to both sides
2(n+1)+1<2n+2

with one more step to show the case for n+1
 
  • #3
Well, it should be possible to show that [itex]2^k+2<2^k \cdot 2[/itex] for some k greater than whatever.

[tex]2< 2\cdot 2^k - 2^k[/tex]
[tex]2< (2-1)2^k[/tex]
[tex]2<2^k[/tex]. From here take the log of both sides, and it shows that [tex]2^k +2 < 2^{k+1}[/tex] holds for all k > 1, which is fine because we're only considering from n=3. So since that's the case and [tex]2(n+1)+1 < 2^n +2 < 2^{n+1}[/tex] this should complete the proof?
 
  • #4
i think that does it, but if you're happy upto
2(n+1)+1<2n+2

then just using, that for n>1
2<2n

should pretty much complete above

ps. i think itspretty much the same reasoning, though just a little clearer in order
 

What is the concept of an inequality proof by induction?

An inequality proof by induction is a mathematical technique used to prove that a statement or inequality is true for all possible values of a variable. It involves breaking the statement down into smaller cases and then using mathematical induction to prove each case.

Why is induction used to prove inequalities?

Induction is a powerful technique for proving inequalities because it allows us to prove that a statement is true for all possible values of a variable, rather than just a few specific cases. This makes for a more rigorous and convincing proof.

What are the steps involved in a simple proof of inequality by induction?

The steps involved in a simple proof of inequality by induction are:

  1. Base case: Prove that the statement is true for the smallest possible value of the variable.
  2. Inductive hypothesis: Assume that the statement is true for some arbitrary value of the variable.
  3. Inductive step: Use the inductive hypothesis to prove that the statement is also true for the next value of the variable.
  4. Conclusion: Since the statement is true for the smallest value and for the next value, it is true for all subsequent values of the variable.

Can induction be used to prove all inequalities?

No, induction can only be used to prove inequalities that follow a certain pattern or can be expressed in terms of a variable. It cannot be used to prove inequalities that are not related to a variable, such as geometric inequalities.

What are some tips for successfully proving an inequality by induction?

Some tips for successfully proving an inequality by induction include:

  1. Start with the base case and make sure it is true.
  2. Clearly state and use the inductive hypothesis.
  3. Be organized and keep track of your steps.
  4. Practice and familiarize yourself with common patterns in inequality proofs.

Similar threads

  • Calculus and Beyond Homework Help
Replies
6
Views
965
  • Calculus and Beyond Homework Help
Replies
15
Views
974
  • Calculus and Beyond Homework Help
Replies
4
Views
738
  • Calculus and Beyond Homework Help
Replies
11
Views
985
  • Calculus and Beyond Homework Help
Replies
7
Views
302
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
23
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
969
Back
Top