# Thread: recursive to explicit equations

1. ## 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?

2. $\displaystyle U_n=a^{n-1}c+b\sum_{i=0}^{n-2}a^i$, easy induction proof.

3. 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}$