1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Induction Proof

  1. Jan 16, 2015 #1
    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:
    [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: Jan 16, 2015
  2. jcsd
  3. Jan 16, 2015 #2

    Mark44

    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}##.
     
  4. Jan 16, 2015 #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
     
  5. Jan 16, 2015 #4

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Have you heard of proof by contradiction?
     
  6. Jan 16, 2015 #5
    I have and I wish. But we're required to prove this directly using induction
     
  7. Jan 16, 2015 #6

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    There's no rule that says you can't use a contradiction argument as part of proving the inductive step!
     
  8. Jan 16, 2015 #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.
     
  9. Jan 16, 2015 #8

    PeroK

    User Avatar
    Science Advisor
    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}##

    Where does that lead?
     
  10. Jan 16, 2015 #9

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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
     
  11. Jan 17, 2015 #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: Jan 17, 2015
  12. Jan 17, 2015 #11

    Mark44

    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.
     
  13. Jan 17, 2015 #12
    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
     
  14. Jan 17, 2015 #13

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

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

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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: Jan 17, 2015
  16. Jan 17, 2015 #15

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Induction Proof
  1. Inductive proof (Replies: 9)

  2. Proof by induction (Replies: 2)

  3. Proof by induction (Replies: 9)

  4. Proof by induction (Replies: 32)

  5. Proof by Induction (Replies: 6)

Loading...