Results 1 to 6 of 6

Math Help - Removing recursion from sequence

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    4

    Removing recursion from sequence

    I think this is the right section since sequences belong to discrete math. Anyway, I have this sequence and I need to know if there is any way to remove the recursion from it:

    {a}_{1} = 1
    {a}_{n} = 2 * {a}_{n-1} + 3*n

    I tried to somehow turn it into exponential function but I don't know how, then I thought about moving something to the other side but I don't think it would work either. Is it even possible to write it without recursion?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45
    The characteristic equation of a_n-2a_{n-1}=0 is \lambda-2=0 so, its solutions are a_n=C2^n . A particular solution of the complete has the form An+B ... etc .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,738
    Thanks
    644
    Hello, Bivalgo!

    a_1 \:=\:1,\;\;a_n \:=\: 2a_{n-1} + 3n

    We have: . a_1 = 1,\;a_2 = 8,\;a_3 = 25,\;a_4 = 62\;\hdots

    \begin{array}{cccccccc}\text{We are given:} & a_n &=& 2a_{n-1} + 3n & [1] \\ \text{Next equation:} & a_{n+1} &=& 2a_n + 3(n\!+\!1) & [2] \end{array}

    \text{Subtract [2] - [1]: }\:a_{n+1} - a_n \;=\;2a_n - 2a_{n-1} + 3

    \begin{array}{cccccccc}\text{And we have:} & a_{n+1} - 3a_n + 2a_{n-1} + 3 &=& 0 & [3] \\ \text{Next equation:} &  a_{n+2} - 3a_{n+1} + 2a_n + 3 &=& 0 & [4] \end{array}

    \text{Subtract [4] - [3]: }\;a_{n+2} - 4a_{n+1} + 5a_n - 2a_{n-1} \;=\;0

    \text{Let }X^n = a_n\!:\;\;X^{n+2} - 4X^{n_1} + 5X^n - 2X^{n-1} \;=\;0

    \text{Divide by }X^{n-1}\!:\;\;X^3 - 4X^2 + 5X - 2 \;=\;0

    \text{Factor: }\;(X - 1)(X - 1)(X - 2) \:=\:0 \quad\Rightarrow\quad X \:=\:1,\:1,\:2

    \text{The formula is: }\;f(n) \;=\;A(1^n) + Bn(1^n) + C(2^n)


    \text{Use the first three terms of the sequence to create a system of equations.}

    . . \begin{array}{cccccccc} f(1) = 1\!: & A + B + 2C &=& 1 & [5] \\ f(2) = 8\!: & A + 2B + 4C &=& 8 & [6] \\ f(3) = 25\!: & A + 3B + 8C &=& 25 & [7] \end{array}

    \begin{array}{cccccccc}\text{Subtract [6] - [5]:} & B + 2C &=& 7 & [8] \\ \text{Subtract [7] - [6]:} & B + 4C &=& 17 & [9] \end{array}

    \text{Subtract [9] - [8]: }\;2C \:=\:10 \quad\Rightarrow\quad C \:=\:5

    \text{Substitute into [8]: }\;B + 2(5) \:=\:7 \quad\Rightarrow\quad B \:=\:\text{-}3

    \text{Substitute into [5]: }\:A - 3 + 10 \:=\:1 \quad\Rightarrow\qud A \:=\:\text{-}6


    \text{Therefore: }\;f(n) \;=\;-6 - 3n + 5(2^n) \;=\;5\!\cdot\!2^n - 3(n+2)

    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Quote Originally Posted by Bivalgo View Post
    I think this is the right section since sequences belong to discrete math. Anyway, I have this sequence and I need to know if there is any way to remove the recursion from it:

    {a}_{1} = 1
    {a}_{n} = 2 * {a}_{n-1} + 3*n

    I tried to somehow turn it into exponential function but I don't know how, then I thought about moving something to the other side but I don't think it would work either. Is it even possible to write it without recursion?
    Alternative solution via generating functions. (A try)

    First let us define {a}_{0} = 0 .

    Let f(x) be generating function of {a}_{n} .

    So:

    f(x)=\sum_{i = 0}^\infty a_ix^i=x+\sum_{i = 2}^\infty a_{i}x^i=x+\sum_{i = 2}^\infty (2a_{i-1}+3i}x^i)=x+\sum_{i = 2}^\infty 2a_{i-1}+\sum_{i = 2}^\infty 3ix^i=x+2x\sum_{i = 1}^\infty a_ix^i+3x\sum_{i = 2}^\infty ix^{i-1}

    Or:

    f(x)=x+2xf(x)+3x(\frac{1}{(1-x)^2}-1}

    Hence, f(x)=\frac{3x}{(1-x)^3}-\frac{2x}{1-x}

    Or:

    f(x)=3x(1+x+x^2+...)^3-2x(1+x+x^2+...)

    Now, if we find the coefficient of x^n.

    I found that a_n=\frac{3}{2}n(n+1)-2

    But this is a wrong answer!

    Where is my mistake?
    Thank you.
    Last edited by Also sprach Zarathustra; May 29th 2011 at 10:24 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2010
    Posts
    4
    Thank you so much for your help!

    However, there are still few lines that I don't quite understand and I'd appreciate a little further explanation because I'm not really this good with math...

    \begin{array}{cccccccc}\text{We are given:} & a_n &=& 2a_{n-1} + 3n & [1] \\ \text{Next equation:} & a_{n+1} &=& 2a_n + 3(n\!+\!1) & [2] \end{array}

    \text{Subtract [2] - [1]: }\:a_{n+1} - a_n \;=\;2a_n - 2a_{n-1} + 3
    I know that here we calculate the difference between any two neighbouring elements of the sequence...

    \begin{array}{cccccccc}\text{And we have:} & a_{n+1} - 3a_n + 2a_{n-1} + 3 &=& 0 & [3] \\ \text{Next equation:} &  a_{n+2} - 3a_{n+1} + 2a_n + 3 &=& 0 & [4] \end{array}

    \text{Subtract [4] - [3]: }\;a_{n+2} - 4a_{n+1} + 5a_n - 2a_{n-1} \;=\;0
    Now me move everything to the left, create second equation with incremented variable and substract the left sides to get another equation...

    \text{Let }X^n = a_n\!:\;\;X^{n+2} - 4X^{n_1} + 5X^n - 2X^{n-1} \;=\;0
    Here's the first thing I don't get - why do we turn n-th element of the sequence into n-th power of X?

    \text{Divide by }X^{n-1}\!:\;\;X^3 - 4X^2 + 5X - 2 \;=\;0
    I understand that here we divide every element by X^(n-1) to simplify the equation as much as possible...

    \text{Factor: }\;(X - 1)(X - 1)(X - 2) \:=\:0 \quad\Rightarrow\quad X \:=\:1,\:1,\:2
    Now we figure out the three possible values of X in this equation...

    \text{The formula is: }\;f(n) \;=\;A(1^n) + Bn(1^n) + C(2^n)
    And here's my other problem. Why do we raise the values of X to n-th power? Why is this function a sum of these powers anyway? And why is B multiplied by n, but A and C are not?

    \text{Use the first three terms of the sequence to create a system of equations.}
    Okay, the rest is obvious - we figure out the value of A, B and C and we get the function.

    Sorry for the lack of correct English terms here and there.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    See this theorem about the solution of a linear homogeneous recurrence relation with constant coefficients.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recursion sequence, and its limit
    Posted in the Calculus Forum
    Replies: 1
    Last Post: December 4th 2009, 04:15 AM
  2. [SOLVED] Limit of a sequence - recursion
    Posted in the Calculus Forum
    Replies: 0
    Last Post: December 4th 2009, 12:54 AM
  3. simplify by removing factors of 1
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 21st 2009, 01:37 PM
  4. Removing (log) from an equality
    Posted in the Algebra Forum
    Replies: 3
    Last Post: June 22nd 2008, 07:24 PM

Search Tags


/mathhelpforum @mathhelpforum