Results 1 to 3 of 3

Math Help - recursive to explicit equations

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    22

    recursive to explicit equations

    is there a way of turning recursive equations of the form U_{n+1}=aU_{n}+b where n_{1}=c into an explicit form with variables a, b and c?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Nov 2006
    From
    Florida
    Posts
    228
    U_n=a^{n-1}c+b\sum_{i=0}^{n-2}a^i, easy induction proof.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,683
    Thanks
    615
    Hello, Rubberduckzilla!

    I know one way . . . it's rather long . . .


    Is there a way of turning recursive equations of the form . U_{n+1}\:=\:aU_{n}+b
    where U_{1}\:=\:c into an explicit form with variables a, b\text{ and }c ?
    The first term is: . U_1 \:=\:c . . . The second term is: . U_2 \:=\:ac+b


    \begin{array}{ccccc}\text{We have the equation:} & U_{n+1} &=& aU_n + b & {\color{blue}[1]} \\<br />
\text{The next equation is:} & U_{n+2} &=& aU_{n+1} + b & {\color{blue}[2]} \end{array}

    Subtract {\color{blue}[2] - [1]}\!: \;\;U_{n+2} - U_{n+1} \;=\;aU_{n+1} - aU_n

    . . and we have: . U_{n+2} - (a+1)U_{n+1} + aU_n


    Let: . X^n \:=\:U_n\!:\quad X^{n+2} - (a+1)X^{n+1} +aX^n \;=\;0

    Divide by X^n\!:\quad X^2 - (a+1)X + a \;=\;0

    . . which factors: . (X - a)(X - 1) \;=\;0

    . . and has roots: . X \;=\;a,\:1

    Hence, the function contains: . a^n \text{ and }1^n

    The function is of the form: . f(n) \;=\;A\!\cdot a^n + B


    We determine A and B by using the first two terms of the sequence.

    \begin{array}{ccccccc}f(1) \:=\:c\!: & Aa + B &=& c & {\color{blue}[3]}\\ f(2) \:=\:ac+b\!: & Aa^2 + B &=& ac + b & {\color{blue}[4]}\end{array}

    Subtract {\color{blue}[4] - [3]}\!:\quad Aa^2 - Aa \:=\:ac + b - c

    . . Aa(a-1) \:=\:ac+b - c \quad\Rightarrow\quad A \;=\;\frac{ac+b-c}{a(a-1)}

    Substitute into {\color{blue}[3]}\!:\frac{ac+b-c}{a(a-1)}\cdot a + B\:=\:c \quad\Rightarrow\quad B \;=\;\frac{\text{-}b}{a-1}


    Therefore: . f(n) \;=\;\frac{ac+b-c}{a(a-1)}\,a^n - \frac{b}{a-1}

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: November 25th 2010, 04:11 AM
  2. Replies: 5
    Last Post: February 22nd 2010, 01:41 PM
  3. Recursive and Explicit Equations...How to Write Them?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 10th 2009, 05:14 PM
  4. Primitive Recursive vs Recursive Functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 29th 2009, 07:32 AM
  5. explicit sequence
    Posted in the Calculus Forum
    Replies: 2
    Last Post: July 31st 2008, 02:18 PM

Search Tags


/mathhelpforum @mathhelpforum