# Induction Proof

## Homework Statement

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

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

Mark44
Mentor

## Homework Statement

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

## 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.
Hat1324 said:
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 * 3k, and use what you have already assumed in your induction hypothesis (i.e., that 3k ≥ n*2n.
Hat1324 said:

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

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
Homework Helper
Gold Member
Have you heard of proof by contradiction?

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

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

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
Homework Helper
Gold Member
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}##

BvU
Homework Helper
2019 Award
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

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:
Mark44
Mentor
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.
Hat1324 said:
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.

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

Ray Vickson
Homework Helper
Dearly Missed

## Homework Statement

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

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

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

BvU
Homework Helper
2019 Award
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 :)

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

Last edited:
BvU
Homework Helper
2019 Award
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.