Proof of Inequalities by Induction.

[rad0786]

Okay, so we are covering proof by induction, and i need some ones help on it covering inequalities.

(a) (2^n) ≤ n! , n≥4

Base Step: sub in n=1 and yes, it works!

Inductinve step: assume (2^n) ≤ n! and show (2^(k+1)) ≤ (k+1)! ,K≥4 holds.

(2^(k+1)) ≤ (k+1)!
(2)(2^k) ≤ (K!)(K+1)
So the bold part is the original equation. In the above, the left side was multiplied by 2 and the right side was multiplied by (K+1). So, anything multiplied by 2 is less than anything multiplied by (K+1), K≥4. Is this proof reasonable?
---------------------------
I initially tried this:

(2^(k+1))
= 2(2^K)
= ?
= ?
≤ (k+1)!

What I am trying to show is to work my way from (2^(k+1)) by expanding it and eventually show that it is less that (K+1)!

somebody care to comment?

Thanks

 

[VietDao29]

So you need to prove:
2^{k + 1} <= (k + 1)!, right?
$$2 ^ {k + 1} = 2 . 2 ^ k \leq 2 . k!$$
Can you show that:
$$2 . k! < (k + 1) . k!$$?
Hint: How is 2 compared to (k + 1) (greater, less than or equal to?), if k >= 4?
----------------------

Base Step: sub in n=1 and yes, it works!

By the way, your base step is wrong.
No, it does not work!
n should be 4 not 1. look at the problem again to see why n must be 4.

Inductinve step: assume (2^n) ≤ n! and show (2^(k+1)) ≤ (k+1)! ,K≥4 holds.

This is wrong, too, why are you assuming that (2^n) ≤ n!, and trying to prove that (2^(k+1)) ≤ (k+1)! ? There is no relation between this inequality (2^n) ≤ n! and this (2^(k+1)) ≤ (k+1)!
You must assume (2^k) ≤ k! (i.e, it's k, not n). Then you can use this inequality to prove (2^(k+1)) ≤ (k+1)!
Do you understand this?
Can you go from here?

 

[rad0786]

So you need to prove:
2^{k + 1} <= (k + 1)!, right?
$$2 ^ {k + 1} = 2 . 2 ^ k \leq 2 . k!$$
Can you show that:
$$2 . k! < (k + 1) . k!$$?
Hint: How is 2 compared to (k + 1) (greater, less than or equal to?), if k >= 4?
----------------------
By the way, your base step is wrong.
n should be 4 not 1. look at the problem again to see why n must be 4.
Can you go from here?

How did you go from:

2^{k + 1} <= (k + 1)!
to
$$2 ^ {k + 1} = 2 . 2 ^ k \leq 2 . k!$$

you mean

2^{k + 1} <= (k + 1)!
to
(2)(2^K) ≤ (K+1)(K!)

i think i don't understand how (k + 1)! became (2)(K!)

-----

$$2 . k! < (k + 1) . k!$$.

This is true because 2 is less than (K+1)!

Ooops, my base step should have been for n >= 4, not n>=1. :)

 

[rad0786]

This is wrong, too, why are you assuming that (2^n) ≤ n!, and trying to prove that (2^(k+1)) ≤ (k+1)! ? There is no relation between this inequality (2^n) ≤ n! and this (2^(k+1)) ≤ (k+1)!
You must assume (2^k) ≤ k! (i.e, it's k, not n). Then you can use this inequality to prove (2^(k+1)) ≤ (k+1)!
Do you understand this?
Can you go from here?

Oh i see what you mean!

 

[VietDao29]

Oh i see what you mean!

So have you worked out the problem?

 

[rad0786]

So have you worked out the problem?

I think so!

Prove (2^n) ≤ n! , n≥4 by induction

BASE STEP: sub in n=4 and yes, it works!

INDUCTIVE STEP: assume (2^k) ≤ k! and prove (2^(k+1)) ≤ (k+1)!

(2^(k+1)) ≤ (k+1)!
(2)(2^k) ≤ (k!)(k+1)

and since the left side is multiplied by 2 and the right side by (k+1), and 2 ≤ (k+1), this means that the right side MUST be greater then the left. Thus, the inequality is proved by induction! is this now correct?

 

[VietDao29]

Looks about right.
But don't forget to add the fact that : 2^k <= k!(induction hypothesis), to this part of your proof:

and since the left side is multiplied by 2 and the right side by (k+1), and 2 ≤ (k+1), and 2^k <= k!(induction hypothesis), this means that the right side MUST be greater then the left. Thus, the inequality is proved by induction! is this now correct?

Other than that, everything looks right. Congratulations... :)

 

[rad0786]

thanks so much :)

 

[HallsofIvy]

But, in your proof (and it would have been better here), don't just say "yes, it works"- show it: 2⁴= 16, 4!= 24 and 16< 24.

Also it would be much better to start with what you KNOW:
$2^k \le k!$ and work to what you want to show:
multiply both sides by 2 to get $2(2^k)= 2^{k+1}\le 2k!$
but, since 1< k, 2< k+1 so 2k!< k!(k+1)= (k+1)!
rather than starting with the result you want and working backwards. That's valid as long as you are careful that each step is reversible but tricky.

 

[rad0786]

Thank you HallsofIvy for your reply!

I personaly find it more difficult to work with what you have to what you want, hence, i find it easier to work backwards.

For instance, prove $n^2 \le n!$ by induction for n=1 and n≥4

Base step:
n = 1, (1)^2 ≤ 1, 1 ≤ 1 ----TRUE
n = 4, (4)^2 ≤ 4!, 16 ≤ 24 ----TRUE

Induction step: (this is where working backwards helps!)

Assume $k^2 \le k!$ and show $(k+1)^2 \le (k+1)!$ for k≥4

$(k+1)^2 \le (k+1)!$
$k^2 + 2k + 1 \le (k+1)(k!)$
$k^2 + (2k +1) \le (k+1)(k!)$

Original equation: $k^2 \le k!$

Since $(2k + 1)$ is being ADDED to the left side of the origingal equation, and $(k + 1)$ is being MULTIPLIED to the right side of the original equation, it holds that the RIGHT side will be GREATER than the LEFT side for k≥4.

Is this a valid proof by induction?

 

[VietDao29]

Since $(2k + 1)$ is being ADDED to the left side of the origingal equation, and $(k + 1)$ is being MULTIPLIED to the right side of the original equation, it holds that the RIGHT side will be GREATER than the LEFT side for k≥4.

Is this a valid proof by induction?

Nope, this part is so wrong.
In fact, you cannot compare addition to multiplication.
So you can work backwards, or forwards, that's up to you. But remember that if you are working backwards, you should pay attention to the fact that everything should be reversible, as HallsofIvy mentioned.
-----------------
So you want to prove that:
$$(k + 1) ^ 2 = k ^ 2 + 2k + 1 \leq (k + 1)! = (k + 1) k! = k! + k \ . \ k!$$ (1) using the fact that:
$$k ^ 2 \leq k!$$.
Looking at the inequality (1), one can say that if they can prove:
$$2k + 1 \leq k . k!$$, then it's done. Do you see why?
Now can you prove that inequality is correct for k >= 4?
Hint: You can again use proof by induction to prove it.
Can you go from here?

 

[ankitkr]

hey... how abt you do this for the inductive step

now u suppose k^2 <= k! for some k>4

then, k+1 = k(1+1/k) < k^2 , since (1+1/k) <= 2 < k.

Thus... (k+1)^2 = (k+1)(k+1) < (k+1)(k^2) <= (k+1)(k!) = (k+1)!


therefore... (k+1)^2 < (k+1)!

hope this helps...

 

[rad0786]

VietDao29: Thank you again, i see what i am doing wrong. I'm getting better at these and feeling more compfortable with these problems!

ankitkr: That answer is the same as the one in the back of the book. it looks messy, id never think of doing that if it were on a test.

Okay, i have 1 last inequality that I want to comfirm with someone. its a bit messy, but here goes:

Prove that for every $n \in N$ their exists a $k \in N$ such that $n \le k^2 \le 2n$.

Base step:
Sub in n=1 to get $1 \le k^2 \le 2$; such a k would be, k=1

Inductive step:

Assume $n \le k^2 \le 2n$ holds and prove $(n+1) \le (k+1)^2 \le 2(n+1)$ for some k

and like I said, i personally find it easier to work with what i want to prove to what i want, hence, work backwards.

$(n+1) \le (k+1)^2 \le 2(n+1)$
$n+1 \le k^2 + 2k +1 \le 2n+2$

$n \le k^2 \le 2n$ is what we have.

$1$ is added to the left side, $2k +1$ is added to the center and $2$ is added to the right side of the equation.

Now i don't have the slightest clue how to compare these? the k term is confusing me, since it can be very flexible.

Perhaps their will allways exsist a number greater than $n+1$ and less than $2n+2$? I am lost now

 

[VietDao29]

I haven't seen this kind of problem before.
Here's my approach, a proof by contradiction.
Assume that the statement is false, then there exists no natural number k such that:
n <= k² <= 2n. That means that there exists some natural number x, such that:
x² < n < 2n < (x + 1)² (noye that: it's less than, not less than or equal to.)
Since everything is positive, take square root of everything gives:
$$x < \sqrt{n} < \sqrt{2n} < x + 1$$.
Form there, we can say that:
$$(x + 1) - x > \sqrt{2n} - \sqrt{n}$$
$$1 > (\sqrt{2} - 1) \sqrt{n}$$
For n >= 3, we have:
$$(\sqrt{2} - 1) \sqrt{n} > 1.01$$.
So that means for n >= 6, we have:
$$1 > (\sqrt{2} - 1) \sqrt{n} > 1.01$$, which implies that 1 > 1.01 (it's wrong, right?)
So we can say for n >= 6, there always exists a natural number k, such that:
n <= k² <= 2n
For n = 1, 2, 3, 4, 5, we can test it manually, and see that it's true.
So for n >= 1, there always exists a natural number k, such that:
n <= k² <= 2n (Q.E.D)
---------------
Do you get it. :)
Now, what does your book have to say? Can you post it here, so that I can help you understand it, and I can know another way to prove it? :)

 

[rad0786]

The book dosn't have an answer/solution for this problem unfortunatly.

It just gives the question: Prove that for every $n \in N$ their exists a $k \in N$ such that $n \le k^2 \le 2n$

Your method looks good an does make sense - it works i think. But is that actually a proof by induction? I thought you can't use contratiction in proofs by induction.

Their is another thread with this same question: https://www.physicsforums.com/showthread.php?t=109362

I havn't tried it yet, however, would breaking up the constraints into its parts work?

 

[rad0786]

Prove that for every $n \in N$ their exists a $k \in N$ such that $n \le k^2 \le 2n$.

Base step:

Sub in n=1 to get $1 \le k^2 \le 2$; such a k would be, k=1

Inductive step:

***Assume $n \le k^2 \le 2n$ holds and prove $(n+1) \le (k)^2 \le 2(n+1)$ for some k***

So we want to show that
$(n+1) \le (k)^2$ and
$(k)^2 \le 2(n+1)$

Suppose that (I previously said that I wasn't sure if contractiction works in this case, but...meh.. a proof is a proof.)

$(n+1) > (k)^2$ and
$(k)^2 > 2(n+1)$

Thus, $(n+1) > (k)^2 > 2(n+1)$ for some k. This implies that $(n+1) > 2(n+1)$ which is False.

Therefore, it holds that $(n+1) \le (k)^2 \le 2(n+1)$ for some k.

This proof sounds good to me!

 

[VietDao29]

Prove that for every $n \in N$ their exists a $k \in N$ such that $n \le k^2 \le 2n$.

Base step:

Sub in n=1 to get $1 \le k^2 \le 2$; such a k would be, k=1

Base step looks good.

Inductive step:

***Assume $n \le k^2 \le 2n$ holds and prove $(n+1) \le (k)^2 \le 2(n+1)$ for some k***

Uhmm, this inductive step is not quite right.
Counter example:
We have: 1 <= 1² <= 2 (this is true). But:
1 + 1 <= 1² <= 2(1 + 1) is false.
So you cannot prove that $(n+1) \le (k)^2 \le 2(n+1)$ using the fact that $n \le k^2 \le 2n$. Since for n = 1, it's false.

So we want to show that
$(n+1) \le (k)^2$ and
$(k)^2 \le 2(n+1)$

Suppose that (I previously said that I wasn't sure if contractiction works in this case, but...meh.. a proof is a proof.)

$(n+1) > (k)^2$ and
$(k)^2 > 2(n+1)$

Meh... this is just so wrong :)
If you want a proof by contradiction, you must first assume what you want to prove is false, then from there arrive at something that's false, hence the statement we've earlier assumed to be false must be true. (Yes, you do this correctly)
Saying this $(n+1) \le (k)^2 \le 2(n+1)$ is the same as saying:
$$k ^ 2 \in \left[ n + 1; \ 2(n + 1) \right]$$, right?
Now assume it's false then:
$$k ^ 2 \notin \left[ n + 1; \ 2(n + 1) \right]$$, that means:
$$k ^ 2 < n + 1$$ or $$k ^ 2 > 2(n + 1)$$ (it's an or, not and). This is where your proof went wrong.
-----------------
So now, you can try breaking up the constraints, and see if it works.
You can read my previous post again, and make sure you understand my proof. Knowing more than 1 way to solve a problem is much better than just knowing 1 way, right?
Now let's try breaking up the constraints... :)