recursive to explicit equations

**Rubberduckzilla** · May 27th 2009, 04:38 PM

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?

**putnam120** · May 27th 2009, 07:36 PM

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

**Soroban** · May 27th 2009, 09:17 PM

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

Thread: recursive to explicit equations

LinkBack

Thread Tools

Display

recursive to explicit equations

Similar Math Help Forum Discussions

How do i find an explicit formula for this recursive linear function?

Generic step by step aproach to convert any recursive formula to explicit.

Recursive and Explicit Equations...How to Write Them?

Primitive Recursive vs Recursive Functions

explicit sequence

Search Tags