Linear recursive sequence in closed-form function

Question

I've been trying to find an answer for a question for some time, and I've done some Google searching but can't seem to figure out exactly how to solve it. It is a linear recursive sequence, and it should be written in a closed-form function.

Problem:

Find the closed form solution for $R_n = -R_{n-1} + 2R_{n-2}$ when $R_0=3$ and $R_1 = 2$

Any help?

Thanks.

Answer 1

$$ R_n + R_{n-1} - 2R_{n-2}=0 $$ Let $R_n = \alpha^n$, then $$\alpha^2 + \alpha - 2 = 0 \implies \alpha = 1 \text{ or } -2$$

$R_n = A + B\cdot(-2)^n$

Plug in $R_0=3, R_1=2$: $$ A+B=3 \\A-2B=2$$

Then the desired closed form is $$ R_n = \frac{8}{3} + \frac{1}{3} (-2)^n $$

Answer 2

Note that $$R_n+2R_{n-1}=R_{n-1}+2R_{n-2}\iff S_n=S_{n-1}$$ where $S_n=R_n+2R_{n-1}$. Since $S_n=S_1=8$, one has $$8=R_n+2R_{n-1}\iff R_n-\frac 83=-2\left(R_{n-1}-\frac 83\right)=\cdots=(-2)^n\left(R_0-\frac 83\right).$$

Answer 3

Let $$f(z) = \sum_{n=0}^\infty R_n z^n.$$ Multiplying the recurrence by $z^n$ and summing over the values of $n$ for which it is valid, the left-hand side is $$\sum_{n=2}^\infty R_n z^n = f(z) - R_0 - R_1z = f(z) -3 -2z, $$ and the right-hand side is $$ \begin{align*} \sum_{n=2}^\infty -R_{n-1}z^n +\sum_{n=2}^\infty 2R_{n-2}z^n &= -z\sum_{n=1}^\infty R_nz^n + 2z^2\sum_{n=0}^\infty R_nz^n\\ &= -z(f(z)-R_0) +2z^2f(z)\\ &= f(z)(2z^2 - z) + 3z. \end{align*} $$ Equating these yields $$ f(z) - 3-2z = f(z)(2z^2-z) + 3z $$ and hence $$\begin{align*} f(z) &= \frac{3+5z}{1 + z - 2z^2}\\ &= \frac{3+5z}{(1-z)(1+2z)}. \end{align*}$$ By partial fraction decomposition we obtain $$ f(z) = \frac83\left(\frac1{1-z}\right) + \frac13\left(\frac1{1+2z}\right), $$ and recognizing this as the sum of two geometric series: $$ f(z) = \frac83\sum_{n=0}^\infty z^n + \frac13\sum_{n=0}^\infty (-2z)^n = \sum_{n=0}^\infty\left(\frac83 + \frac13(-2)^n\right)z^n.$$ It follows that $$ R_n = \frac83 + \frac13(-2)^n.$$