Results 1 to 5 of 5

Math Help - Recurrence Relations

  1. #1
    Junior Member
    Joined
    Apr 2008
    Posts
    37

    Recurrence Relations

    I don't realy understand how to solve recurrence relations. I have the following 2 problems and I don't know how to work them.

    1)
    <br />
a_{n} = 6a_{n-1} - 8a_{n-2}, for n >= 2, a_{0} = 4 a_{1} = 10<br />
    2)
    <br />
a_{n} = 2a_{n-1} - a_{n-2}, for n >= 2, a_{0} = 4 a_{1} = 1<br />
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    #1:

    a_{n}=6a_{n-1}-8a_{n-2}, \;\ a_{0}=4, \;\ a_{1}=10

    We get the quadratic:

    n^{2}-6n+8=0

    (n-4)(n-2)=0

    n=4, \;\ n=2

    a\cdot 4^{n}+b\cdot 2^{n}

    a\cdot 4^{0}+b\cdot 2^{0}=4

    a\cdot 4^{1}+b\cdot 2^{1}=10

    Solve the system and we get:

    a+b=4
    4a+2b=10

    a=1, \;\ b=3

    \boxed{4^{n}+3\cdot 2^{n}}

    Can you get the other?. It has 1 as a root of multiplicity 2, so you will need an extra n:

    a\cdot 1^{n}+b\cdot n\cdot 1^{n}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2008
    Posts
    37
    So for number 2:

    a * 1^0 + b*(0)*1^0 = 4

    so

    a = 4

    a*1^1 + b(1) * 1^1 = 1

    5 + b = 1

    b = -4

    4 * 2^n - 4 * 1^n

    This works for a_0 but not a_1. Where did I go wrong. By the way, thanks so much. Trying to do this on my own and its hard!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    n^{2}-2n+1

    (n-1)^{2}

    The solution(s) is 1 and 1. Remember, I said multiplicity 2?.

    a\cdot 1^{n}+b\cdot n\cdot 1^{n}

    a\cdot 1^{0}+b(0)\cdot 1^{0}=4\Rightarrow a=4

    a\cdot 1^{1}+b(1)\cdot 1^{1}=1\Rightarrow a+b=1

    \therefore a=4, \;\ b=-3

    \boxed{4-3n}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    <br />
a_{k + 2}  = 2 \cdot a_{k + 1}  - a_k  \Leftrightarrow a_{k + 2}  - a_{k + 1}  = a_{k + 1}  - a_k <br />
for all <br />
k \in \mathbb{N}<br />

    Since <br />
a_{k + 2}  - a_{k + 1}  = a_{k + 1}  - a_k <br />
we have that the sequence <br />
b_k  = a_{k + 1}  - a_k <br />
is constant ( that can be done by induction)

    So <br />
a_{k + 1}  - a_k  = a_1  - a_0=1-4=-3 <br />
for all <br />
k \in \mathbb{N}<br />

    Summing: <br />
\sum\limits_{k = 0}^{n - 1} {\left( {a_{k + 1}  - a_k } \right)}  = \left( { - 3} \right) \cdot n<br />

    On the LHS we have a telescoping sum: <br />
\sum\limits_{k = 0}^{n - 1} {\left( {a_{k + 1}  - a_k } \right)}  = \left( {a_1  - a_0 } \right) + \left( {a_2  - a_1 } \right) + ... + \left( {a_{n - 1}  - a_{n - 2} } \right) + \left( {a_n  - a_{n - 1} } \right)<br />

    Cancelling out the terms: <br />
\sum\limits_{k = 0}^{n - 1} {\left( {a_{k + 1}  - a_k } \right)}  = a_n  - a_0  = a_n  - 4 <br />

    So: <br />
a_n  = -3 \cdot n + 4<br />
    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