# General formula for recurrence relation

While studying contest math training notes, I came across this question and wonder what are the techniques for writing closed-form formulas for recurrence relations, and the circumstances in which this is possible.

Suppose $$a_0=0$$, $$b_0=1$$ and that $$a_n=a_{n-1}+2b_{n-1}$$, $$b_n=4b_{n-1}-a_{n-1}$$. Find formulas for $$a_n$$ and $$b_n$$.

I managed to untangle $$a$$ and $$b$$ and came to $$a_n=3a_{n-1}+2^n$$ and $$b_n=3b_{n-1}+2^{n-1}$$ but have no idea how to come up with a formula.

• In general recurrence relations can "often" times be solved using generating functions of some sort - I'm quite confident that they can also be employed in this specific example. It requires you to be confident around series (in particular the cauchy product is often times quite useful and I think you need it here) and know some common ones though (like the geometric series - which you may also run into with this example depending on how you approach it). Commented Jan 11, 2023 at 20:29

Starting from $$a_n=3a_{n-1}+2^n$$, divide both sides by $$2^n$$ to get $$\frac{a_n}{2^n}=\frac32\cdot\frac{a_{n-1}}{2^{n-1}}+1.$$ If we denote $$\dfrac{a_n}{2^n}=c_n$$, then $$c_n=\dfrac32c_{n-1}+1$$. Transform it into $$c_n+2=\frac32\left(c_{n-1}+2\right).$$ Notice that $$c_0+2=\dfrac01+2=2$$, so $$c_n+2=2\cdot\left(\dfrac32\right)^n=\dfrac{3^n}{2^{n-1}}$$. Plug back to get $$a_n=2^n\left(\dfrac{3^n}{2^{n-1}}-2\right)=2\cdot3^n-2^{n+1}.$$ To check the answer, I used the same method to get

$$b_n=2\cdot3^n-2^n.$$

Classical generating functions approach: Introduce $$G( z) = \sum_{n \geq 0} a_{ n}z^{n}$$, multiplying the equation through by $$z^{n}$$ and summing over all $$n\ge 0$$ gives us (set $$a_{ -1} = 0$$) \begin{align*} \sum_{n \geq 0} a_{ n}z^{n}= \sum_{n \geq 0} 3a_{ n - 1}z^{n}+ \sum_{n \geq 0} 2^{n }z^{n} - 1\iff G( z) = 3zG( z) + \frac{1}{1 - 2z} - 1 .\end{align*} Solving for $$G( z)$$ we obtain \begin{align*} G( z) = \frac{1}{( 1 - 2z) ( 1 - 3z) } - \frac{1}{1 - 3z} = \frac{3}{1 - 3z}- \frac{2}{1 - 2z} = 2\sum_{n \geq 0} 3^{n}z^{n} - \sum_{n \geq 0} 2^{n+1}z^{n} \end{align*} yielding \begin{align*} a_{ n} = [ z^{n}] G( z) =2\cdot 3^{n} - 2^{n + 1} .\end{align*} With a similar procedure you can obtain the closed form of $$b _{ n}$$.

A classical way to treat this kind of question is to write the mixed recurrence under a matrix form, here:

$$\begin{pmatrix}a_{n+1}\\b_{n+1} \end{pmatrix}=\begin{pmatrix}1&2\\-1&4\end{pmatrix}\begin{pmatrix}a_{n}\\b_{n} \end{pmatrix} \ \text{with} \ \begin{pmatrix}a_{0}\\b_{0} \end{pmatrix}=\begin{pmatrix}0\\1 \end{pmatrix}$$

or under a condensed form:

$$V_{n+1}=AV_n \ \text{with} \ V_{0}=\begin{pmatrix}0\\1 \end{pmatrix} \ \iff \ V_{n}=A^{n}V_0=PD^nP^{-1}V_0$$

using the diagonalized form of $$A$$ with $$D^n=\begin{pmatrix}3^n&0\\0&2^n \end{pmatrix}$$

(because the eigenvalues of $$A$$ are $$3$$ and $$2$$), $$P$$ being any matrix whose columns are eigenvectors associated, in this order, to $$3$$ and $$2$$.

I leave you the last computations allowing to check that we obtain the same results as those obtained with the two other methods (generating functions and transformation into a single second order recurrence).

Solve the second equation for $$a_n$$ $$a_n = 4 b_n - b_{n+1}$$ plug into the first equation to get $$b_{n+1} = 5 b_n - 6 b_{n-1}$$ now try an ansatz (inspired guess, also known as the method of undetermined parameters) $$b_n = k x^n$$ to get... $$x^2 - 5x + 6 =0$$ which has two solutions for $$x$$ (2 and 3), so $$b_n = k_1(2^n)+k_2(3^n)$$

plug this into the equation $$a_n = 4 b_n - b_{n+1}$$ to get $$a_n = 2k_1(2^n)+k_2(3^n)$$ Now use your initial values to find $$k_1$$ and $$k_2$$