Can Induction Prove 3^n ≥ n2^n for All n ≥ 0?

[Hat1324]

Homework Statement

The question asks me to prove inductively that 3ⁿ ≥ n2ⁿ for all n ≥ 0.

Homework Equations

The Attempt at a Solution

I believe the base case is when n = 0, in which case this is true. However, I cannot for the life of me prove n = k+1 when n=k is true. I start with:
[itex] 3^k ≥ k2^k [/itex]

and then try:
[itex] 3^{k+1} ≥ (k+1)2^{k+1}[/itex] which gets me nowhere.

I then try:
[itex] 3^{k+1} ≥ 3k2^k [/itex]

but I still have no idea where to go from there. Please help :(

Whoops the Latex is all whack. Edit: Thanks

 

[Mark44]

Homework Statement

The question asks me to prove inductively that 3ⁿ ≥ n2ⁿ for all n ≥ 0.

Homework Equations

The Attempt at a Solution

I believe the base case is when n = 0, in which case this is true. However, I cannot for the life of me prove n = k+1 when n=k is true. I start with:
[itex] 3^k ≥ k2^k [/itex]

and then try:
[itex] 3^{k+1} ≥ (k+1)2^{k+1}[/itex] which gets me nowhere.

This is unrelated to what you need to do.

I then try:
[itex] 3^{k+1} ≥ 3k2^k [/itex]

The above is what you need to show, so you can't just start with it.
Start with ##3^{k + 1}## which is the same as 3 * 3^k, and use what you have already assumed in your induction hypothesis (i.e., that 3^k ≥ n*2ⁿ.

but I still have no idea where to go from there. Please help :(

Whoops the Latex is all whack

It's fine, but you were doing it wrong. If an exponent has more than one character, surround it with braces, as in 3^{k + 1}. This renders as ##3^{k + 1}##.

 

[Hat1324]

I think I've explained my steps a little wrong. The first thing I did after the base case was assume [tex]3^k≥k2^k[/tex]

Then I setup [tex]3^{k+1}=3(3k)≥3(k2^k)≥...[/tex]

But I simply cannot find something to substitute ... that is actually true

 

[PeroK]

Have you heard of proof by contradiction?

 

[Hat1324]

I have and I wish. But we're required to prove this directly using induction

 

[PeroK]

There's no rule that says you can't use a contradiction argument as part of proving the inductive step!

 

[Hat1324]

Heh. I'm following as best I can I really don't follow. :P I can't see how [itex] ∃ 3^{k+1} ≤ (k+1)2^{k+1} [/itex] is any easier to disprove than [itex] ∀ 3^{k+1} ≥ (k+1)2^{k+1} [/itex] is to prove.

 

[PeroK]

It's almost always a good idea if you're stuck proving something to turn it round and assume what you're trying to show is false and see where that leads.

So, if:

##3^k > k2^k##

But

##3^{k+1} < (k+1)2^{k+1}##

Where does that lead?

 

[BvU]

I think I've explained my steps a little wrong. The first thing I did after the base case was assume [tex]3^k≥k2^k[/tex]

Then I setup [tex]3^{k+1}=3(3k)≥3(k2^k)≥...[/tex]

But I simply cannot find something to substitute ... that is actually true

Perok calls is contradiction; you could also try what I call working from the other end: write out ##(k+1)2^{k+1}## and see what you can strike off

 

[Hat1324]

OK. I think I have it. So what I ended up doing was brute forcing a base case of ##0 \le n \le 2## and testing it for 0, 1, and 2 (which holds). Then I showed that for all ##k \ge 2##
##3^{k+1} = 3*3^k##
##2^{k+1} = 2*2^k##
##k+1 \le (1.5)k##

This got me to derive ##3^{k+1} \ge (k+1)2^{k+1} \rightarrow (3)3^k \ge (1.5)(2)k2^k## which is ##(3)3^k \ge (3)k2^k## which is obviously true. Does what I did count as induction?

 

[Mark44]

OK. I think I have it. So what I ended up doing was brute forcing a base case of ##0 \le n \le 2## and testing it for 0, 1, and 2 (which holds).

You need only one base case.

Then I showed that for all ##k \ge 2##
##3^{k+1} = 3*3^k##
##2^{k+1} = 2*2^k##
##k+1 \le (1.5)k##

This got me to derive ##(3)3^k \ge (1.5)(2)k2^k## which is ##(3)3^k \ge (3)k2^k## which is obviously true. Does what I did count as induction?

I don't think so. As I said earlier, assume that the statement is true for n = k. Then use this assumption to show that the statement is true for n = k + 1. The work you have done above might be useful in doing this.

 

[Hat1324]

Yeah I know I only need one base case, but I couldn't do the work above without showing n=0,1,2 so I included them anyway

 

[Ray Vickson]

Homework Statement

The question asks me to prove inductively that 3ⁿ ≥ n2ⁿ for all n ≥ 0.

Homework Equations

The Attempt at a Solution

I believe the base case is when n = 0, in which case this is true. However, I cannot for the life of me prove n = k+1 when n=k is true. I start with:
[itex] 3^k ≥ k2^k [/itex]

and then try:
[itex] 3^{k+1} ≥ (k+1)2^{k+1}[/itex] which gets me nowhere.

I then try:
[itex] 3^{k+1} ≥ 3k2^k [/itex]

but I still have no idea where to go from there. Please help :(

Whoops the Latex is all whack. Edit: Thanks

You can write the desired statement as ##(3/2)^n \geq n##; that may be a lot easier to deal with.

 

[BvU]

I think I've explained my steps a little wrong. The first thing I did after the base case was assume [tex]3^k≥k2^k[/tex]

Then I setup [tex]3^{k+1}=3(3k)≥3(k2^k)≥...[/tex]

But I simply cannot find something to substitute ... that is actually true

Let me go back to where you were after the first step: If [itex]3^k≥k2^k[/itex] is true, then you want to prove [itex]3^{k+1}\ge (k+1)2^{k+1}[/itex] and you started well with [itex]3^{k+1}=3\;3^k[/itex].

Now my suggestion (and in fact PerOK's as well) was to write out [itex] (k+1)2^{k+1}[/itex] and see what happens. Not so much as a sequence of ##\ge## , but as a sum of terms you might be able to strike off:$$
(k+1)2^{k+1}= k\;2^{k+1} +2^{k+1}= 2k\;2^k + 2\;2^k
$$Do you see what you can strike off (because it's assumed to satisfy the ##\ge## ) ? And what remains ?

If you can prove that remainder also satisfies the ##\ge## , then you have the ingredients to write it down in a decent sequence of .. is true for k = 0 & if .. then .. , therefore .. is true for all k.

But I think there's a nice little snag built in that forces you to backtrack one step with this approach: it doesn't go smoothly for small k. So you have to bootstrap the induction (true for k = .., .. and from then on induction).

Sorry about the vague description; I don't want to give it all away.

Open for more elegant approaches :)

[edit]Oh boy, Ray's post was right in front of me. More coffee, please...

 

[BvU]

OK. I think I have it. So what I ended up doing was brute forcing a base case of ##0 \le n \le 2## and testing it for 0, 1, and 2 (which holds). Then I showed that for all ##k \ge 2##
##3^{k+1} = 3*3^k##
##2^{k+1} = 2*2^k##
##k+1 \le (1.5)k##

This got me to derive ##3^{k+1} \ge (k+1)2^{k+1} \rightarrow (3)3^k \ge (1.5)(2)k2^k## which is ##(3)3^k \ge (3)k2^k## which is obviously true. Does what I did count as induction?

More egg , since you did as I suggested, and did quite well.

Let me recapitulate (a chance for still more egg :) ):

To me it counts as induction, especially if you write it down in a neat order:

You need to prove ##P_k : 3^k > k 2^k ## for all k ##\ge 0.## You show ##P_0, P_1, P_2## and for k ##\ge## 2 you show
$$P_k \Rightarrow 3\; 3^k \ge 3k\;2^k \Rightarrow 3^{k+1} \ge 1.5\;k\;2^{k+1} \Rightarrow 3^{k+1} \ge (k+1)\;2^{k+1} = P_{k+1}$$Therefore ##P_k \; \forall {k\ge 0} ##

It's a slightly liberal interpretation of what my (1971!) math book calls 'an analogon of full induction' : if ##P_{n_0}## for a certain integer ##n_0##, and .. etc.