Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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
    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!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook