Express the sequence $\{x_n\}$ where $x_n = 2x_{n-1} + 3x_{n-2}$ in terms of ${x_0, x_1, n}$

Question

Given a sequence $\{x_n\}$ where $x_n = 2x_{n-1} + 3x_{n-2}$ how can one express it in terms of ${x_0, x_1, n}$. Can this be generalized for ${x_n = \alpha x_{n-1} + \beta x_{n-2}}$

I've tried to use the following approach: $$\eqalign{ & 1x_0 = x_01 \\ & zx_1 = x_1z \\ & z^2x_2 = (2x_1 + 3x_0)z^2 \\ & z^3x_3 = (2x_2 + 3x_1)z^3 \\ & z^4x_4 = (2x_3 + 3x_2)z^4 \\ & ... \\ & z^nx_n = (2x_{n-1} + 3x_{n-2})z^n }$$

Then sum LHS with RHS which will produce:

$${ x_0 + \sum\limits_{k = 1 }^na_nz^n = x_0 +zx_1 + 2\sum\limits_{k = 2}^nx_{n-1}z^n + 3 \sum\limits_{k = 2}^n x_{n-2}z^n }$$

Let $${ G(z) = x_0 + \sum\limits_{k = 1 }^na_nz^n }$$

Then RHS may be expressed in terms of ${G(z)}$. For example $${ 2\sum\limits_{k = 2}^na_{n-1}z^n = 2z\sum\limits_{k = 2}^na_{n-1}z^{n-1} = 2z(\sum\limits_{k = 1}^na_{n}z^{n} + x_0 - x_0) = 2z(G(z) - x_0) }$$

Applying those transformations I eventually got ${G(z)}$ expressed in terms of z and ${x_1, x_0}$. But at this point I got stuck.

I got a sum of fractions: $${ \frac{3x_0 - x_1}{4(1+z)}+\frac{x_0+x_1}{4(1-3z)} }$$

I guess i could expand the fractions into series and find their sum, but i am not supposed to know about such expansions at the point of the book i took the problem from.

All of the above feels like a wrong approach. So the question is whether this can be done in a more elegant way.

Answer 1

Solving recurrence relations is actually very similar to solving ODEs. For simplicity, lets stick with the general second order recurrence relation

$$a_n=\alpha a_{n-1}+\beta a_{n-2}$$

Firstly, observe that if $a_n=f(x_0,x_1,n)$ and $a_n=g(x_0,x_1,n)$ are both solutions, then $a_n=(f+g)(x_0,x_1,n)$ is also a solution.

Now, we guess the solution $a_n=\lambda^n$ for some constant $\lambda$ to be determined. Plugging this in:

\begin{align} \ & a_n=\alpha a_{n-1}+\beta a_{n-2} \\ \ \implies & \lambda^n=\alpha \lambda^{n-1}+\beta \lambda^{n-2} \\ \ \implies & \lambda^2-\alpha\lambda-\beta=0 \end{align}

i.e. $\lambda$ is a root to this quadratic. Let the two roots of this quadratic be $\lambda_1$ and $\lambda_2$. Then the general solution would be

$$a_n=A\lambda_1^n+B\lambda_2^n$$

where the constants $A$ and $B$ are to be determined by the initial conditions. As per your question with the general case, if $a_0=a_0$ and $a_1=a_1$, then we have

$$a_0=a_0 \implies a_0=A+B$$

$$a_1=a_1 \implies a_1=A\lambda_1+B\lambda_2$$

and we solve for $A$ and $B$ from here.

---

In your example where you had the recurrence relation

$$a_n=2a_{n-1}+3a_{n-2}$$

By guessing the solution $a_n=\lambda^n$, we arrive at the quadratic

$$\lambda^2-2\lambda-3=0$$

giving the roots $\lambda_1=3$ and $\lambda_2=-1$. Thus, the general solution is

$$a_n=A\cdot 3^n+B\cdot (-1)^n$$

Plugging in $n=0$ and $n=1$, we get

$$a_0=A+B \qquad a_1=3A-B$$

Hence $A=\frac{a_0+a_1}{4}$ and $B=\frac{3a_0-a_1}{4}$, giving

$$a_n=\frac{a_0+a_1}{4}\cdot 3^n+\frac{3a_0-a_1}{4}\cdot (-1)^n$$

Answer 2

Let $f(x)$ be the generating function for some sequence $(a_{n})_{n\in\mathbb{N}}$ such that \begin{align*} f(x)=\frac{c}{bx+d}=\sum^{\infty}_{n=0}{a_{n}x^{n}},\ c,b,d\in\mathbb{Z}.\tag{1} \end{align*} Then \begin{alignat*}{3} f(x)=\frac{c}{bx+d}&\implies f^{\prime}(x) &&=-1!\left(\frac{b}{c}\right)^{1}f(x)^{2}\\ &\implies f^{\prime\prime}(x) &&=+2!\left(\frac{b}{c}\right)^{2}f(x)^{3}\\ &\implies f^{\prime\prime\prime}(x) &&=-3!\left(\frac{b}{c}\right)^{3}f(x)^{4}\\ &\qquad &&\vdots\\ &\implies f^{n}(x) &&=(-1)^{n}n!\left(\frac{b}{c}\right)^{n}\big(f(x)\big)^{n+1}, \end{alignat*}

where $f^{n}(x)$ denotes the $n^{\text{th}}$ derivative of $f$ with respect to $x.$ If we evaluate $f^{n}(0)$, the Maclaurin series expansion of $f(x)$ is then given by

\begin{alignat*}{4} &\qquad \qquad \qquad \qquad \quad f^{n}(0)&&=(-1)^{n}n!\left(\frac{b}{c}\right)^{n}f(0)^{n+1}\\ & &&=(-1)^{n}n!\left(\frac{b}{c}\right)^{n}\left(\frac{c}{d}\right)^{n+1}\\ &\qquad \qquad \qquad \quad \implies f(x) &&=\sum_{n=0}^{\infty }c\ (-1)^{n}\left(\frac{1}{d}\right)^{n+1}{b^{n}x^{n}}.\tag{2}\\ \end{alignat*} It follows from (1) and (2) that the explicit form of the sequence $(a_{n})_{n\in\mathbb{N}}$ is given by \begin{align*}a_{n}=c\ (-1)^{n}\left(\frac{1}{d}\right)^{n+1} b^{n}.\tag{3}\\ \end{align*}
If we let $c=x_{0}+x_{1},\ b=-12,$ and $d=4$, as in (1) then

\begin{alignat*}{3} g(x)=\frac{x_{0}+x_{1}}{4-12z}&\overset{(3)}{\implies} g_{n}&&=(-1)^{n}(x_{0}+x_{1})(-12)^{n}\left(\frac{1}{4}\right)^{n+1}\\ &\qquad &&=(x_{0}+x_{1})(-1)^{n}(-1)^{n}(3)^{n}(4)^{n}\left(\frac{1}{4}\right)^{n}\left(\frac{1}{4}\right)\\ &\ \implies g_{n} &&=\left(\frac{1}{4}\right)3^{n}(x_{0}+x_{1}).\tag{4} \end{alignat*} Similarly \begin{alignat*}{3} h(x)=\frac{3x_{0}-x_{1}}{4+4z}&\overset{3}{\implies} h_{n}&&=(-1)^{n}(3x_{0}-x_{1})(4)^{n}\left(\frac{1}{4}\right)^{n+1}\\ &\qquad &&=(3x_{0}-x_{1})(-1)^{n}(4)^{n}\left(\frac{1}{4}\right)^{n}\left(\frac{1}{4}\right)\\ &\ \implies h_{n} &&=(-1)^{n}\left(\frac{1}{4}\right)(3x_{0}-x_{1}).\tag{5}\\ \end{alignat*} It follows from the linearity of differentiation, (superposition principle), that we may combine (4) and (5) to obtain the desired formula for $x_{n}$. Whence,

\begin{align}x_{n}=\left(\frac{1}{4}\right)3^{n}(x_{0}+x_{1})+ (-1)^{n}\left(\frac{1}{4}\right)(3x_{0}-x_{1})\tag*{$\square$}\end{align}

Answer 3

Consider the matrix:

$$ X_n = \begin{bmatrix} x_{n+2} & x_{n+1} \\ x_{n+1} & x_{n} \end{bmatrix} $$

Then there is a recurrence relation:

$$X_{n+1} = X_n \begin{bmatrix} 2 & 1 \\ 3 & 0 \end{bmatrix} $$

So we may say that

$$X_{n} = X_0 \begin{bmatrix} 2 & 1 \\ 3 & 0 \end{bmatrix}^{n} = X_0A^n$$

Through whatever method you'd like to use, realize the eigenvectors of $A$ are $(-1, 3)$ and $(1, 1)$, with values $-1$ and $3$. Thus through a change of basis,

$$A = \begin{bmatrix} -1 & 1 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} -1 & 0 \\ 0 & 3 \end{bmatrix} \begin{bmatrix} -1 & 1 \\ 3 & 1 \end{bmatrix}^{-1} = \begin{bmatrix} -1 & 1 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} -1 & 0 \\ 0 & 3 \end{bmatrix} \begin{bmatrix} -1/4 & 1/4 \\ 3/4 & 1/4 \end{bmatrix} $$ and $$ A^n = \begin{bmatrix} -1 & 1 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} -1 & 0 \\ 0 & 3 \end{bmatrix}^n \begin{bmatrix} -1/4 & 1/4 \\ 3/4 & 1/4 \end{bmatrix} = \begin{bmatrix} -1 & 1 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} (-1)^n & 0 \\ 0 & 3^n \end{bmatrix} \begin{bmatrix} -1/4 & 1/4 \\ 3/4 & 1/4 \end{bmatrix} $$ Finally, let $x_0 = 0$ (or whatever, it don't matter) so that $$ X_0= \begin{bmatrix} x_2 & x_1 \\ x_1 & x_0 \end{bmatrix}$$ Then multiplying, (the top-right and bottom-left elements are actually equal) $$ X_n= \begin{bmatrix} \dfrac{3^{n+1}(x_2 + x_1) - (-1)^{n}(3x_1 - x_2)}{4} & \dfrac{3^{n}(x_2 + x_1) + (-1)^{n}(3x_1 - x_2)}{4} \\ \dfrac{3^{n+1}(x_1 + x_0) - (-1)^{n}(3x_0 - x_1)}{4} & \dfrac{3^{n}(x_1 + x_0) + (-1)^{n}(3x_0 - x_1)}{4} \end{bmatrix} $$ The bottom right element is $x_n$. Thus, $$x_n = \frac{3^{n}(x_1 + x_0) + (-1)^{n}(3x_0 - x_1)}{4}$$

Answer 4

Use generating functions. Define $g(z) = \sum_{n \ge 0} x_n z^n$, take the recurrence shifted by 2, multiply by $z^n$ and sum over $n \ge 0$, recognize resulting sums:

$\begin{align*} \sum_{n \ge 0} x_{n + 2} z^n &= 2 \sum_{n \ge 0} x_{n + 1} z^n + 3 \sum_{n \ge 0} x_n z^n \\ \frac{g(z) - x_0 - x_1 z}{z^2} &= 2 \frac{g(z) - x_0}{z} + 3 g(z) \end{align*}$

Solve for $g(z)$, write as partial fractions; extract coefficient of $z^n$:

$\begin{align*} g(z) &= \frac{x_0 + (x_1 - 2 x_0) z}{1 - 2 z - 3 z^2} \\ &= \frac{x_0 + x_1}{4 (1 - 3 z)} + \frac{3 x_0 - x_1}{4 (1 + z)} \\ x_n &= [z^n] g(z) \\ &= \frac{x_0 + x_1}{4} \cdot 3^n + \frac{3 x_0 - x_1}{4} \cdot (-1)^n \end{align*}$

The last because the series is:

$\begin{align*} \sum_{n \ge 0} a^n z^n &= \frac{1}{1 - a z} \end{align*}$