• Support PF! Buy your school textbooks, materials and every day products Here!

Induction Proof

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

Answers and Replies

  • #2
33,305
4,998

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
7
0
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
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
12,438
5,180
Have you heard of proof by contradiction?
 
  • #5
7
0
I have and I wish. But we're required to prove this directly using induction
 
  • #6
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
12,438
5,180
There's no rule that says you can't use a contradiction argument as part of proving the inductive step!
 
  • #7
7
0
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
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
12,438
5,180
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
BvU
Science Advisor
Homework Helper
2019 Award
13,048
3,023
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
7
0
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
33,305
4,998
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
7
0
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
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728

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
BvU
Science Advisor
Homework Helper
2019 Award
13,048
3,023
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
BvU
Science Advisor
Homework Helper
2019 Award
13,048
3,023
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.
 

Related Threads on Induction Proof

  • Last Post
Replies
1
Views
803
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
4
Views
1K
Replies
2
Views
1K
Replies
13
Views
2K
  • Last Post
Replies
6
Views
735
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
9
Views
1K
Replies
2
Views
4K
Top