# Induction Proof

Tags:
1. Jan 16, 2015

### Hat1324

1. The problem statement, all variables and given/known data
The question asks me to prove inductively that 3n ≥ n2n for all n ≥ 0.

2. Relevant equations

3. 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$

Whoops the Latex is all whack. Edit: Thanks

Last edited: Jan 16, 2015
2. Jan 16, 2015

### Staff: Mentor

This is unrelated to what you need to do.
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 * 3k, and use what you have already assumed in your induction hypothesis (i.e., that 3k ≥ n*2n.
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}$.

3. Jan 16, 2015

### 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

4. Jan 16, 2015

### PeroK

Have you heard of proof by contradiction?

5. Jan 16, 2015

### Hat1324

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

6. Jan 16, 2015

### PeroK

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

7. Jan 16, 2015

### 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.

8. Jan 16, 2015

### 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}$

9. Jan 16, 2015

### BvU

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

10. Jan 17, 2015

### 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?

Last edited: Jan 17, 2015
11. Jan 17, 2015

### Staff: Mentor

You need only one base case.
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.

12. Jan 17, 2015

### Hat1324

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

13. Jan 17, 2015

### Ray Vickson

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

14. Jan 17, 2015

### BvU

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 :)

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

Last edited: Jan 17, 2015
15. Jan 17, 2015

### BvU

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.