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!

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


    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]
    [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