1. Not finding help here? Sign up for a free 30min 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!

Proof by induction

  1. Jan 5, 2009 #1
    1. The problem statement, all variables and given/known data
    Define the numbers a(0),a(1),a(2),...by a(0)=1, a(1)=3, a(n)=4[a(n-1) - a(n-2)]. for n>=2
    Show by induction that for all n>=1, a(n)=2^(n-1) [n+2]



    2. Relevant equations



    3. The attempt at a solution

    proof by induction is not my stong point, and i really don't know where to start on this question. Any help would be much appreciated!
     
  2. jcsd
  3. Jan 5, 2009 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Re: proo

    One nice thing about induction is you always know "where to start"- prove the statement is true for n= 0!

    Then you will really want to use "strong induction": If, whenever a statement is true for all k less than n, it true for k= n, then the statement is true for all positive integers.

    If the statement is true for all k< n, it is, in particular true for n-1 and n-2: you can assume that
    [tex]a(n-1)= 2^{n-1-1}(n-1+ 2)= 2^{n-2}(n+1)[/tex]
    and
    [tex]a(n-2)= 2^{n-2-1}(n-2+2)= 2^{n-3}n[/tex]

    Put those into a(n)= 4[a(n-1)- a(n-2)] and see what you get.
     
  4. Jan 5, 2009 #3
    Re: proo

    thanks for the help!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof by induction
  1. Proof by induction (Replies: 2)

  2. Proof by induction (Replies: 9)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...