Proof By Induction/Inequation

[Wanderer]

Hello, there. I'm not really sure whether this thread belongs here, so I apologize if it's in the wrong place. I'm having a hard time making progress with this:

Prove by induction that for all natural numbers n, n≥4:

2ⁿ ≥ n²

I'm fine with the base step. Then, I make the assumption that it's true for n=k.

But trying to go from 2^k ≥ k² to:

2^k+1 ≥ (k+1)² is really baffling me. I've tried multiplying both sides by 2, giving:

2^k+1 ≥ 2k²

Would it be sufficient to show that 2k² ≥ (k+1)², I wonder? And if so, how would I go about doing that? If not, I'm completely lost.

 

[JeffM]

Hello, there. I'm not really sure whether this thread belongs here, so I apologize if it's in the wrong place. I'm having a hard time making progress with this:

Prove by induction that for all natural numbers n, n≥4:

2ⁿ ≥ n²

I'm fine with the base step. Then, I make the assumption that it's true for n=k.

But trying to go from 2^k ≥ k² to:

2^k+1 ≥ (k+1)² is really baffling me. I've tried multiplying both sides by 2, giving:

2^k+1 ≥ 2k²

Would it be sufficient to show that 2k² ≥ (k+1)², I wonder? And if so, how would I go about doing that? If not, I'm completely lost.

I don't know if this is an invariably successful method, but I have found that it works frequently.

You want to show that \(\displaystyle 2^{(k + 1)} \ge k^{(2 + 1)}\ given\ 2^k \ge k^2\ and\ k \ge 4.\)

So the first thing I would do is to express both expressions in terms of k.

\(\displaystyle 2^{(k + 1)} = 2 * 2^k = 2^k + 2^k.\) I have things in term of 2^k.

\(\displaystyle (k + 1)^2 = k^2 + 2k + 1.\)

Now, by assumption, \(\displaystyle 2^k \ge k^2.\) But what about the second \(\displaystyle 2^k\ and\ 2k + 1.\)

Oh my, you need a lemma. Do you see what lemma you need?

Can you finish the problem now?

If not, do you understand how we got to where we are now?

 

[Wanderer]

I don't know if this is an invariably successful method, but I have found that it works frequently.

You want to show that \(\displaystyle 2{(k + 1)} \ge k^{(2 + 1)}\ given\ 2^k \ge k^2\ and\ k \ge 4.\)

So the first thing I would do is to express both expressions in terms of k.

\(\displaystyle 2^{(k + 1)} = 2 * 2^k = 2^k + 2^k.\) I have things in term of 2^k.

\(\displaystyle (k + 1)^2 = k^2 + 2k + 1.\)

Now, by assumption, \(\displaystyle 2^k \ge k^2.\) But what about the second \(\displaystyle 2^k\ and\ 2k + 1.\)

Oh my, you need a lemma. Do you see what lemma you need?

Can you finish the problem now?

If not, do you understand how we got to where we are now?

Thanks for the response. I'm still not quite there yet. Writing everything in terms of k does sound like a good idea, and I can follow the steps that you've taken. What's left then is to prove that \(\displaystyle 2^k \ge 2k + 1\). I'm not sure how to approach this. What are these mystical llamas that you speak so fondly of?

 

[JeffM]

Thanks for the response. I'm still not quite there yet. Writing everything in terms of k does sound like a good idea, and I can follow the steps that you've taken. What's left then is to prove that \(\displaystyle 2^k \ge 2k + 1\). EXACTLY. I'm not sure how to approach this. What are these mystical llamas that you speak so fondly of?

I like the joke

The one L lama is a priest
The two L llama is a beast

But a three elama is a bad conflagration. Hat tip to Ogden Nash.

A lemma is a result that you need to prove the result you REALLY want to prove.

So we need on a preliminary basis to demonstrate that

\(\displaystyle n \in \mathbb N\ and\ n \ge 4 \implies 2^n \ge 2n + 1.\)

Let's use induction.

First step: \(\displaystyle 2^4 = 16 > 9 = 8 + 1 = 2 * 4 + 1.\)

Now what is the second step in proving the lemma?

Now can you do the whole thing? (By the way, there may be an easier way. I don't know. But I wanted to show you what I have found to be a very useful method generally.)

So, being formal, you first demonstrate your lemma and then demonstrate your actual theorem. Of course in practice you find out you need the lemma by trying to do the main proof and reaching a point where you say "But how do I prove that?".

 

[lookagain]

I don't know if this is an invariably successful method, but I have found that it works frequently.

You want to show that > > > \(\displaystyle 2{(k + 1)} \ge k^{(2 + 1)}\ given\ 2^k \ge k^2\ and\ k \ge 4.\) < < <

JeffM, I'm pretty sure you meant to type the following instead of what you did (highlighted) above:



"You want to show that \(\displaystyle \ \ 2^{(k + 1)} \ \ge \ (k + 1)^2 \ \ \ given \ \ \ 2^k \ \ge \ k^2 \ \ \ and \ \ \ k \ \ge \ 4."\)

 

[JeffM]

JeffM, I'm pretty sure you meant to type the following instead of what you did (highlighted) above:



"You want to show that \(\displaystyle \ \ 2^{(k + 1)} \ \ge \ (k + 1)^2 \ \ \ given \ \ \ 2^k \ \ge \ k^2 \ \ \ and \ \ \ k \ \ge \ 4."\)

Yes lookagain. Thank you kindly for pointing out my error. I shall correct it.

 

[Wanderer]

Hello, there. Let's give this another stab. Also, if my notation is off, please correct me because I've just been dissolved in new letters and symbols so I'm still trying to get my head around them.

Proof:

\(\displaystyle 2^n \ge (2n + 1) \forall n\in \mathbb{N},n\ge~4\)

Let n = 4.

Then, we have:

\(\displaystyle 2^4 \ge 2(4) + 1\)

\(\displaystyle 16 > 9\)

Assume true for n=k:

\(\displaystyle 2^k\ge~2k+1\)

Induction hypothesis: if true for n=k+1:

\(\displaystyle 2^{k+1}\ge 2(k+1) + 1\)

\(\displaystyle 2^{k+1}\ge 2k+3\)

This seems a lot less horrifying than my original problem, but I'm still not quite there.

Starting from \(\displaystyle 2^k \ge 2k + 1\) and multiplying by 2:

\(\displaystyle 2^{k+1} \ge 4k + 2\)

Now, I can't make much progress from here. I did wonder whether I could have a 'lemma within a lemma' (a second lemma?) and show to begin that \(\displaystyle 4n + 2 \ge 2n + 3~\forall n\in\mathbb{N}\), which can be done with simple algebra:

We need: \(\displaystyle 4n + 2 \ge 2n + 3\)

Which happens when: \(\displaystyle 2n \ge 1\)

\(\displaystyle n \ge\frac{1}{2}\) and as \(\displaystyle n\in\mathbb{N}\) must be \(\displaystyle \ge{1}\), this is true for all n.

Would I be able to then use this to prove the first lemma, as \(\displaystyle 2^{k+1} \ge 4k + 2\implies 2^{k+1}\ge 2k + 3\)? If so, having proved the first lemma, I can easily go on to solve the whole induction problem. But one has to wonder whether there isn't an easier way, particularly since the other problems haven't taken anywhere near as long...?

 

[JeffM]

Hello, there. Let's give this another stab. Also, if my notation is off, please correct me because I've just been dissolved in new letters and symbols so I'm still trying to get my head around them.

Proof:

\(\displaystyle 2^n \ge (2n + 1) \forall n\in \mathbb{N},n\ge~4\)

Let n = 4.

Then, we have:

\(\displaystyle 2^4 \ge 2(4) + 1\)

\(\displaystyle 16 > 9\)

Assume true for n=k:

\(\displaystyle 2^k\ge~2k+1\)

Induction hypothesis: if true for n=k+1:

\(\displaystyle 2^{k+1}\ge 2(k+1) + 1\)

\(\displaystyle 2^{k+1}\ge 2k+3\)

This seems a lot less horrifying than my original problem, but I'm still not quite there.

Starting from \(\displaystyle 2^k \ge 2k + 1\) and multiplying by 2:

\(\displaystyle 2^{k+1} \ge 4k + 2\)

Now, I can't make much progress from here. I did wonder whether I could have a 'lemma within a lemma' (a second lemma?) and show to begin that \(\displaystyle 4n + 2 \ge 2n + 3~\forall n\in\mathbb{N}\), which can be done with simple algebra:

We need: \(\displaystyle 4n + 2 \ge 2n + 3\)

Which happens when: \(\displaystyle 2n \ge 1\)

\(\displaystyle n \ge\frac{1}{2}\) and as \(\displaystyle n\in\mathbb{N}\ge{1}\), this is true for all n.

Would I be able to then use this to prove the first lemma, as \(\displaystyle 2^{k+1} \ge 4k + 2\implies 2^{k+1}\ge 2k + 3\)? If so, having proved the first lemma, I can easily go on to solve the whole induction problem. But one has to wonder whether there isn't an easier way, particularly since the other problems haven't taken anywhere near as long...?

First off, I admit that the method I have been showing you may not be the quickest. What I like about it is that it provides a method that pretty consistently works and so gives a starting point.

\(\displaystyle Prove:2^n \ge 2n + 1\ \forall\ n \ge 4 \in \mathbb N.\)

\(\displaystyle 2^4 = 16\ and\ 2 * 4 + 1 = 9 \implies 2^4 \ge 2 * 4 + 1.\)

\(\displaystyle So\ \exists\ k\ |\ k \in \mathbb N\ and\ k \ge 4\ and\ 2^k \ge 2k + 1.\)

Now what I am recommending is to express the expressions for k + 1 in terms of the corresponding expressions for k. So

\(\displaystyle 2^{(k + 1)} = 2 * 2^k.\)

\(\displaystyle 2(k + 1) + 1 = 2k + 2 + 1 = (2k + 1) + 2.\)

What next?

Well I know that \(\displaystyle 2^k \ge (2k + 1).\) And I can break \(\displaystyle 2 * 2^k\ up\ into\ 2^k + 2^k.\) Can I show \(\displaystyle 2^k > 2?\)

Back to formal proof.

\(\displaystyle But\ 2 * 2^k = 2^k + 2^k.\)

\(\displaystyle k \ge 4 > 1 \implies 2^k > 2^1 = 2 \implies 2^k \ge 2.\)

\(\displaystyle 2^k \ge (2k + 1)\ and\ 2^k > 2 \implies 2^k + 2^k \ge (2k + 1) + 2 \implies 2^{(k+1)} \ge 2(k + 1) + 1.\)

Now this is not an elegant presentation and it may not be in the required format, but you can pretty it up and you have proved your lemma.

 

[Deleted member 4993]

I like the joke

The one L lama is a priest
The two L llama is a beast

And I will bet
A silk pajama
There isn't any
Three-l lllama.

 

[lookagain]

Prove by induction that for all natural numbers n, n≥4:

2ⁿ ≥ n²

I'm fine with the base step. Then, I make the assumption that it's true for n=k.

But trying to go from 2^k ≥ k² to:

2^k+1 ≥ (k+1)² is really baffling me. I've tried multiplying both sides by 2, giving:

2^k+1 ≥ 2k²

Would it be sufficient to show that 2k² ≥ (k+1)², I wonder? \(\displaystyle \ \ \ \) Yes!

And if so, how would I go about doing that? If not, I'm completely lost.

If you show \(\displaystyle \ 2k^2 \ \ge \ (k + 1)^2, \) * \(\displaystyle \ \) then your train will be:


\(\displaystyle 2^{k + 1} \ \ge \ 2k^2 \ \ge \ (k + 1)^2\)


\(\displaystyle So \ \ then \ \ 2^{k + 1} \ \ge \ (k + 1)^2 \ \ \) would be the conclusion.


Because of this, then, there really is no need to go down that road and prove the lemma that \(\displaystyle \ 2^k \ \ge \ 2k + 1 \ \ \) (for appropriate k).

(But you do still need to show * above.)

 

[Wanderer]

If you show \(\displaystyle \ 2k^2 \ \ge \ (k + 1)^2, \) * \(\displaystyle \ \) then your train will be:


\(\displaystyle 2^{k + 1} \ \ge \ 2k^2 \ \ge \ (k + 1)^2\)


\(\displaystyle So \ \ then \ \ 2^{k + 1} \ \ge \ (k + 1)^2 \ \ \) would be the conclusion.


Because of this, then, there really is no need to go down that road and prove the lemma that \(\displaystyle \ 2^k \ \ge \ 2k + 1 \ \ \) (for appropriate k).

(But you do still need to show * above.)

Right. I think I'm just about there with JeffM's method now (so yay, and thanks!), but I'm curious about how one would approach doing things like this. I have a horrible feeling it's going to involve some other lemma or inductive process, though, so I'm almost scared to ask.

Going inductively, I can show it's true for n=4, say. Then, making the assumption that it's true for \(\displaystyle n=k\) gives the assumption that:

\(\displaystyle 2k^2\ge (k+1)^2\)
or:
\(\displaystyle 2k^2\ge k^2 + 2k + 1\)

The hypothesis to prove then is:

\(\displaystyle 2(k+1)^2\ge (k+2)^2\)
or:
\(\displaystyle 2k^2 + 4k + 2\ge k^2 + 4k + 4\)

But again, there doesn't seem to be an easy road to travel here. Simply adding the appropriate extras to the assumption gives something rather unlike the target. For example, starting with the assumption:

\(\displaystyle 2k^2 \ge k^2 + 2k + 1\)

Add \(\displaystyle 4k + 2\) to both sides to give desired LHS:

\(\displaystyle 2k^2 + 4k + 2 \ge k^2 + 6k + 3\)

\(\displaystyle 2(k+1)^2 \ge (k+2)^2 + 2k - 1\)

Hm. Then, I wonder whether it's enough to state that \(\displaystyle 2k - 1 > 0\) as \(\displaystyle k\in\mathbb{N}\), meaning that we have:

\(\displaystyle 2(k+1)^2 \ge (k+2)^2 + A\), where A>0, hence, \(\displaystyle 2(k+1)^2 \ge (k+2)^2\) ??

If so, I think I've shown all that's necessary to bypass the llama?!

 

[JeffM]

Right. I think I'm just about there with JeffM's method now (so yay, and thanks!), but I'm curious about how one would approach doing things like this. I have a horrible feeling it's going to involve some other lemma or inductive process, though, so I'm almost scared to ask.

Going inductively, I can show it's true for n=4, say. Then, making the assumption that it's true for \(\displaystyle n=k\) gives the assumption that:

\(\displaystyle 2k^2\ge (k+1)^2\)
or:
\(\displaystyle 2k^2\ge k^2 + 2k + 1\)

The hypothesis to prove then is:

\(\displaystyle 2(k+1)^2\ge (k+2)^2\)
or:
\(\displaystyle 2k^2 + 4k + 2\ge k^2 + 4k + 4\)

But again, there doesn't seem to be an easy road to travel here. Simply adding the appropriate extras to the assumption gives something rather unlike the target. For example, starting with the assumption:

\(\displaystyle 2k^2 \ge k^2 + 2k + 1\)

Add \(\displaystyle 4k + 2\) to both sides to give desired LHS:

\(\displaystyle 2k^2 + 4k + 2 \ge k^2 + 6k + 3\)

\(\displaystyle 2(k+1)^2 \ge (k+2)^2 + 2k - 1\)

Hm. Then, I wonder whether it's enough to state that \(\displaystyle 2k - 1 > 0\) as \(\displaystyle k\in\mathbb{N}\), meaning that we have:

\(\displaystyle 2(k+1)^2 \ge (k+2)^2 + A\), where A>0, hence, \(\displaystyle 2(k+1)^2 \ge (k+2)^2\) ??

If so, I think I've shown all that's necessary to bypass the llama?!

Looks good to me. No one REALLY wants lemmas, lamas, llamas, or silk pajamas.

There are frequently many ways to prove a statement.

 

[Nehushtan]

I've tried multiplying both sides by 2, giving:

2^k+1 ≥ 2k²

Note that the quadratic expression \(\displaystyle k^2-2k-1=(k-1)^2-2\) attains it minimum value (of \(\displaystyle -2\)) at \(\displaystyle k=1\); thereafter it is strictly increasing. In particular it is strictly increasing for \(\displaystyle k\geqslant4\). Now when \(\displaystyle k=4\) the expression is nonnegative (\(\displaystyle 4^2-2\cdot4-1=7\geqslant0\)). Hence we have \(\displaystyle k^2-2k-1\geqslant0\) for \(\displaystyle k\geqslant4\) i.e. \(\displaystyle k^2\geqslant2k+1\) for \(\displaystyle k\geqslant4\).

Therefore \(\displaystyle 2^{k+1}\geqslant2k^2=k^2+k^2\geqslant k^2+2k+1=(k+1)^2\) for \(\displaystyle k\geqslant4\).

 

[Wanderer]

We reviewed the exercise in class today. There was indeed a shorter solution:

Starting from the assumption:

\(\displaystyle 2^k \ge k^2\)

\(\displaystyle 2^{k+1} \ge 2k^2\)

And by definition here, \(\displaystyle k\ge 4\), which means \(\displaystyle k^2 \ge 4k\) so:

\(\displaystyle 2^{k+1} \ge 2k^2 = k^2 + k^2 \ge k^2 + 4k\)

\(\displaystyle 2^{k+1} \ge k^2 + 4k\)

\(\displaystyle 2^{k+1} \ge k^2 + 2k + 2k\)

And as \(\displaystyle k\ge 4\):

\(\displaystyle 2^{k+1} \ge k^2 + 2k + 8\)

\(\displaystyle 2^{k+1} \ge k^2 + 2k + 1\)

\(\displaystyle 2^{k+1} \ge (k+1)^2\)

Which was the induction hypothesis. Still, I'm grateful for all of these solutions, none of which were 'bad' as far as I can tell. I don't really feel like there was any 'obvious' way to tackle this, but maybe I'm just inexperienced...