Results 1 to 2 of 2

Math Help - help with recurrence relations

  1. #1
    Newbie
    Joined
    Aug 2008
    Posts
    15

    help with recurrence relations

    Solve the following recurrence relation for a

    a) an=3an-1-3an-2+an-3 a0=a1=1, a2=2

    then

    b) find and solve a recurrence relation for the number of ways to make a pile of n chips using red, white and blue chips and such that no two red chips are together.

    Thanks for your help, i keep getting stuck
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,868
    Thanks
    747
    Hello, dixie!

    Here's the first part . . .


    Solve the following recurrence relation for a.

    . . a_n\:=\:3a_{n-1}-3a_{n-2}+a_{n-3} \qquad a_0 = a_1 = 1,\;\;a_2=2
    We conjecture that: a(n) = X^n, an exponential function.

    Then we have: . X^n \:=\:3X^{n-1} - 3X^{n-2} + X^{n-3}

    Divide by X^{n-3}\!:\;\;X^3 \:=\:3X^2 - 3X + 1 \quad\Rightarrow\quad X^3 - 3X^2 + 3X - 1 \:=\:0

    . . . . . . . (X - 1)^3 \:=\:0\quad\Rightarrow\quad X \:=\:1,1,1


    The function is of the form: . a(n) \;=\;A + Bn + Cn^2

    . . \begin{array}{cccccccc}<br />
a(0) = 1\!: & A+B(0) + C(0^2) &=& 1 & \Rightarrow & A &=&1 \\<br />
a(1) = 1\!: & A + B(1)+C(1^2) &=&1 & \Rightarrow & A + B + C &=&1 \\<br />
a(2) = 2\!: & A + B(2)+C(2^2) &=&2 & \Rightarrow & A + 2B + 4C &=&2 \end{array}

    Solve the system of equations: . A = 1,\;\;B = \text{-}\frac{1}{2},\;\;C = \frac{1}{2}


    Therefore: . a(n) \;=\;1 - \frac{1}{2}n + \frac{1}{2}n^2 \quad\Rightarrow\quad\boxed{ a(n) \;=\;\frac{n^2 - n + 2}{2}}

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: July 28th 2011, 03:50 PM
  2. Recurrence relations
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: February 24th 2011, 10:45 AM
  3. Recurrence relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 1st 2010, 07:59 AM
  4. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 08:56 PM
  5. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 11th 2008, 12:57 AM

Search Tags


/mathhelpforum @mathhelpforum