Solve the following recurrences using generating functions.

Question

Solve the following recurrence using generating functions to find a formula for $A_n$ in terms of $n$.

$A_0 = 1$, $A_1 = 1$, and for $n\geq 2$, $A_n = A_{n-1} + 2A_{n-2} + 4$

Answer 1

Consider the function \begin{align} f(x) & = \sum_{n=0}^{\infty}a_nx^n = 1 + x + \sum_{n=0}^{\infty} a_{n+2} x^{n+2} = 1 + x + \sum_{n=0}^{\infty}\left(a_{n+1} + 2a_n + 4\right)x^{n+2}\\ & = 1 + x + \sum_{n=0}^{\infty}a_{n+1}x^{n+2} + 2 \sum_{n=0}^{\infty}a_nx^{n+2} + 4 \sum_{n=0}^{\infty}x^{n+2}\\ & = 1 + x + \dfrac{f(x)-1}x + 2x^2 f(x) + \dfrac{4x^2}{1-x} \tag{$\star$} \end{align} Solve for $f(x)$ from $(\star)$ and develop the Taylor series to get $a_n$.

Another way is as follows. Let $b_n = A_n - a$. We then have$$b_n + a = b_{n-1} + a + 2b_{n-2} + 2a + 4 \implies b_n = b_{n-1} + 2b_{n-2} + 2a + 4$$ Choose $a=-2$, to get $$b_n = b_{n-1} + 2b_{n-2}$$ Now the recurrence relation is linear, homogeneous and has constant coefficients and a standard way is to solve it as follows: First obtain the characteristic equation. To do this, assume $b_n = m^n$. Plug it in to get a quadratic in $m$. Solve for $m$. Get the two roots say $m_1$ and $m_2$. Now the general solution is given by the linear combination, i.e., $b_n = a_1 m_1^n + a_2 m_2^n$. Solve for $a_1$ and $a_2$ using the initial conditions.

For your recurrence, the corresponding equation becomes, $$m^2-m-2 = 0 \Rightarrow (m-2)(m+1) = 0$$ This gives us $$b_n = a \cdot 2^n + b\cdot (-1)^n$$ where $a$ and $b$ are obtained from the initial conditions. In our case, $b_0 = b_1 = 3$. This gives us $$a+b = 3 = 2a-b \implies a = 2 \text{ and } b = 1$$Hence,$$a_n = 2^{n+1} + (-1)^{n} -2$$This methodology is analogous to plugging in $y=e^{mx}$ when you want to solve a linear, homogeneous ODE with constant coefficients. Here you have a difference equation instead of a differential equation.