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:
3^k ≥ k2^k

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

I then try:
3^{k+1} ≥ 3k2^k

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:
3^k ≥ k2^k

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

This is unrelated to what you need to do.

I then try:
3^{k+1} ≥ 3k2^k

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 3^k≥k2^k

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

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 ∃ 3^{k+1} ≤ (k+1)2^{k+1} is any easier to disprove than ∀ 3^{k+1} ≥ (k+1)2^{k+1} 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 3^k≥k2^k

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

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:
3^k ≥ k2^k

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

I then try:
3^{k+1} ≥ 3k2^k

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 3^k≥k2^k

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

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 3^k≥k2^k is true, then you want to prove 3^{k+1}\ge (k+1)2^{k+1} and you started well with 3^{k+1}=3\;3^k.

Now my suggestion (and in fact PerOK's as well) was to write out (k+1)2^{k+1} 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.