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

In summary: The first step is to assume that the statement is true for n = k.The second step is to use this assumption to show that the statement is true for n = k + 1.
  • #1
Hat1324
7
0

Homework Statement


The question asks me to prove inductively that 3n ≥ n2n 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
 
Last edited:
Physics news on Phys.org
  • #2
Hat1324 said:

Homework Statement


The question asks me to prove inductively that 3n ≥ n2n 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.
Hat1324 said:
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 * 3k, and use what you have already assumed in your induction hypothesis (i.e., that 3k ≥ n*2n.
Hat1324 said:
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}##.
 
  • #3
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
 
  • #4
Have you heard of proof by contradiction?
 
  • #5
I have and I wish. But we're required to prove this directly using induction
 
  • #6
There's no rule that says you can't use a contradiction argument as part of proving the inductive step!
 
  • #7
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.
 
  • #8
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?
 
  • #9
Hat1324 said:
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
 
  • #10
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:
  • #11
Hat1324 said:
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.
 
  • #12
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
 
  • #13
Hat1324 said:

Homework Statement


The question asks me to prove inductively that 3n ≥ n2n 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.
 
  • #14
Hat1324 said:
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, o:) Ray's post was right in front of me. More coffee, please...
 
Last edited:
  • #15
Hat1324 said:
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 o:), 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.
 

1. What is induction proof?

Induction proof is a mathematical method used to prove a statement for all natural numbers. It involves showing that the statement holds for the first natural number (usually 0 or 1) and then showing that if it holds for any given natural number, it will also hold for the next natural number.

2. How is induction proof different from other methods of proof?

Induction proof is different from other methods of proof, such as direct proof or proof by contradiction, because it relies on the concept of recursion and building up from smaller cases to prove a statement for all cases.

3. What are the steps of an induction proof?

The steps of an induction proof are as follows: 1) Show that the statement holds for the first natural number. 2) Assume that the statement holds for some arbitrary natural number (known as the "induction hypothesis"). 3) Use the induction hypothesis to prove that the statement also holds for the next natural number. 4) Conclude that the statement holds for all natural numbers by the principle of mathematical induction.

4. Can any statement be proven using induction?

No, not all statements can be proven using induction. Induction can only be used to prove statements that are true for all natural numbers, and cannot be used for statements that involve real or complex numbers.

5. What are some common mistakes to avoid when using induction proof?

Some common mistakes to avoid when using induction proof include: 1) Forgetting to prove the statement for the first natural number. 2) Assuming the statement is true for all natural numbers without proving it. 3) Using the wrong base case. 4) Using the wrong induction hypothesis. 5) Not using the principle of mathematical induction to conclude the proof.

Similar threads

  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
916
  • Calculus and Beyond Homework Help
Replies
3
Views
537
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
493
  • Calculus and Beyond Homework Help
Replies
23
Views
1K
  • Calculus and Beyond Homework Help
Replies
13
Views
1K
Back
Top