recursive to explicit equations

Hello, Rubberduckzilla!

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

Quote:

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