Mathematical Induction: Proving Inequalities with k and k+1

[gfd43tg]

Homework Statement

Homework Equations

The Attempt at a Solution

Hello, I am working on the problem in the attached image regarding induction based on the inequality

$$2^n \geq n + 1$$

I am confused how to do this by proving that if it is assumed to be true for $n = k$, then how it is true for $n = k + 1$. The way I see it, you would just do $2^{k+1} \geq (k+1) + 1$. The answer is $2(k+1) \geq k + 2$, but I do not understand it.

 

[bloby]

Hello, for inline latex $\#\$# before and after the expression.
'You would just do' : not exactly, it is what you have to prove assuming $2^k \geq k+1$ holds.

 

[HakimPhilo]

Hint:
Let $a,b,c,d$ be four positive numbers such that $a\gt b$ and $c\gt d$, then we have: $$ac\gt bd.$$ For your particular example you have $2^{k}\geqslant k+1$ and you need to find a relation $c\gt d$ such that when you apply the above rule you get $$2^{k+1}\geqslant (k+1)+1.$$ Can you find such relation and prove it?

 

[gfd43tg]

So are you saying in this case for $a > b$, then $a = 2^k$ and $b = k+1$. Then I need a $c$ and $d$. Well, I think $c$ would be equal to $2$, but I need something such that $d*(k+1) = k + 2$.

Hence
$$d = k+2/k+1$$

Then it follows
$$ac \geq bd$$

Thus,
$$2(2^k) \geq (k+1)(k+2/{k+1})$$
$$2^{k+1} \geq k+2$$

 

[HakimPhilo]

You got it right for $c$, can you now solve the equation $d(k+1)=k+2$ for $d$?

 

[gfd43tg]

I got it now, but how the heck would I ever know to do that? I would have never guessed that would be the way to prove it. How is it logical to approach the problem in that manner? Also, how do I get the k+1 to be on the bottom of the fraction?

 

[HakimPhilo]

Response to your edited post:

You now found the relation $c\gt d$ to go from $2^k\geqslant k+1$ to $2^{k+1}\geqslant k+2$. But you still need to prove that relation, do you know how to proceed?

I got it now, but how the heck would I ever know to do that? I would have never guessed that would be the way to prove it. How is it logical to approach the problem in that manner? Also, how do I get the k+1 to be on the bottom of the fraction?

You got $k+1$ in the bottom of the fraction by solving for $d$: $$d(k+1)=k+2\implies\require{cancel}d\cancel{(k+1)}\dfrac{1}{\cancel{k+1}}=(k+2)\dfrac1{k+1}\implies d=\dfrac{k+2}{k+1}.$$ The approach to this problem boils down to figuring out a way to go from $2^k\geqslant k+1$ into $2^{k+1}\geqslant k+2$. It's basically just what AlephZero did but written in a more detailed manner.

 

[AlephZero]

I would have never guessed that would be the way to prove it.

Neither would I

On the other hand, if you assume $2^k \ge k + 1$ and you want to show that $2^{k+1} \ge (k+1) + 1$, then

$2^{k+1} = 2(2^k) \ge 2(k+1) =2k +2 \ge k + 2$ when $k \ge 0$.

 

[gfd43tg]

Yes, for $c > d$, you get $2 \geq k+2/k+1$, which by algebraic manipulation is $2(k+1) \geq k+2$. How do I get the fraction to look like yours, with the fraction being on the bottom? As well as the slash going through indicating canceling a term.

 

[HakimPhilo]

Yes, for $c > d$, you get $2 \geq k+2/k+1$, which by algebraic manipulation is $2(k+1) \geq k+2$. How do I get the fraction to look like yours, with the fraction being on the bottom? As well as the slash going through indicating canceling a term.

For the fraction use \frac{}{} for example \frac{x+2}{x+1} will produce $\frac{x+2}{x+1}$. For the slash you first have to write \require{cancel} then to use the \cancel{} command where you put what you want to slash inside the brackets, therefore \require{cancel}\cancel{x+1} will produce $\require{cancel}\cancel{x+1}$.

 

[LCKurtz]

It's basically just what AlephZero did but written in a more detailed manner.

I wouldn't call it "detailed". I would describe it a very confusing explanation which isn't very helpful for understanding the simple induction step.

 

[HakimPhilo]

I wouldn't call it "detailed". I would describe it a very confusing explanation which isn't very helpful for understanding the simple induction step.

I could have proceeded as AlephZero (which is what I originally did but then got a warning with my post being deleted) but the OP specifically mentions that he didn't know where the need for $2(k+1) \geqslant k + 2$ came from.