Results 1 to 5 of 5

Thread: 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)
    $\displaystyle
    a_{n} = 6a_{n-1} - 8a_{n-2}, for n >= 2, a_{0} = 4 a_{1} = 10
    $
    2)
    $\displaystyle
    a_{n} = 2a_{n-1} - a_{n-2}, for n >= 2, a_{0} = 4 a_{1} = 1
    $
    Follow Math Help Forum on Facebook and Google+

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

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

    We get the quadratic:

    $\displaystyle n^{2}-6n+8=0$

    $\displaystyle (n-4)(n-2)=0$

    $\displaystyle n=4, \;\ n=2$

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

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

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

    Solve the system and we get:

    $\displaystyle a+b=4$
    $\displaystyle 4a+2b=10$

    $\displaystyle a=1, \;\ b=3$

    $\displaystyle \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:

    $\displaystyle 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,002
    Thanks
    1
    $\displaystyle n^{2}-2n+1$

    $\displaystyle (n-1)^{2}$

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

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

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

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

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

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

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

    Since $\displaystyle
    a_{k + 2} - a_{k + 1} = a_{k + 1} - a_k
    $ we have that the sequence $\displaystyle
    b_k = a_{k + 1} - a_k
    $ is constant ( that can be done by induction)

    So $\displaystyle
    a_{k + 1} - a_k = a_1 - a_0=1-4=-3
    $ for all $\displaystyle
    k \in \mathbb{N}
    $

    Summing: $\displaystyle
    \sum\limits_{k = 0}^{n - 1} {\left( {a_{k + 1} - a_k } \right)} = \left( { - 3} \right) \cdot n
    $

    On the LHS we have a telescoping sum: $\displaystyle
    \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)
    $

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

    So: $\displaystyle
    a_n = -3 \cdot n + 4
    $
    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: Jul 28th 2011, 02:50 PM
  2. Recurrence relations
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: Feb 24th 2011, 09:45 AM
  3. Recurrence relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Dec 1st 2010, 06:59 AM
  4. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 6th 2009, 07:56 PM
  5. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Feb 10th 2008, 11:57 PM

Search Tags


/mathhelpforum @mathhelpforum