Results 1 to 3 of 3

Thread: 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 $\displaystyle U_{n+1}=aU_{n}+b$ where $\displaystyle 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
    $\displaystyle 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
    12,028
    Thanks
    848
    Hello, Rubberduckzilla!

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


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


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

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

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


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

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

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

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

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

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


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

    $\displaystyle \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 $\displaystyle {\color{blue}[4] - [3]}\!:\quad Aa^2 - Aa \:=\:ac + b - c$

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

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


    Therefore: .$\displaystyle 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: Nov 25th 2010, 04:11 AM
  2. Replies: 5
    Last Post: Feb 22nd 2010, 01:41 PM
  3. Recursive and Explicit Equations...How to Write Them?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 10th 2009, 05:14 PM
  4. Primitive Recursive vs Recursive Functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jan 29th 2009, 07:32 AM
  5. explicit sequence
    Posted in the Calculus Forum
    Replies: 2
    Last Post: Jul 31st 2008, 02:18 PM

Search Tags


/mathhelpforum @mathhelpforum