# Trying to solve a recurrence relation by using generating functions: $a_n=3a_{n-1} + a_{n-2}$

I'm trying to solve the recurrence relation below by using generating function:

$$$$a_n=\begin{cases} 0, & \text{if n<0}\\ 2, & \text{if n=0}\\ 1, & \text{if n=1}\\ 3a_{n-1} + a_{n-2}, & \text{otherwise}. \end{cases}$$$$

The first thing I did was make the recurrence relation valid for all $$n$$ by using a kronecker delta:

$$a_0 = 3.(0) + 0 + 2.(\delta_{n,0}) = 2$$

$$a_1 = 3.(2) + 0 - 5.(\delta_{n,1}) = 1$$

The result I got was:

$$a_n = 3a_{n-1} + a_{n-2} + 2\delta_{n,0} - 5\delta_{n,1}$$

Multiplying by $$x^n$$:

$$a_n . x^n = 3a_{n-1} . x^n + a_{n-2} . x^n + 2\delta_{n,0} . x^n - 5\delta_{n,1} . x^n$$

Summing up both sides:

$$\sum_{n\geq0} a_n . x^n = \sum_{n\geq0}3a_{n-1} . x^n + \sum_{n\geq0}a_{n-2} . x^n + \sum_{n\geq0}2\delta_{n,0} . x^n - \sum_{n\geq0}5\delta_{n,1} . x^n$$

And making $$F(x) = \sum_{n\geq0} a_n . x^n$$, I got:

$$F(x) = 3xF(x) + x^2F(x) + 2 - 5x$$

which is:

$$F(x) = \frac{2 - 5x}{1-3x-x^2}$$

So far so good but from here on I can't find a way to calculate the $$a_n$$

I've heard it has something to do with partials fractions but I'm a newbie in this subject and I have no idea how to follow through.

Does anyone can help me to finish the calculation?

Thanks in advance.

## 3 Answers

I'm going to rewrite the problem as $$a_{n+2} = 3a_{n+1} + a_n; \; a_0 = 2,\; a_1=1.$$ Multiply by $$x^n$$, sum, and let $$A(x) = \sum_{n\ge 0}a_nx^n$$. So, $$\sum_{n\ge 0}a_{n+2}x^n = 3\sum_{n\ge 0}a_{n+1}x^n + \sum_{n\ge 0}a_n x^n,$$ and we can see that $$\sum_{n\ge 0}a_{n+2}x^n = a_2 + a_3x + \cdots = (1/x^2)(A(x)-a_0-a_1x)$$ and similarly $$\sum_{n\ge 0}a_{n+1}x^n = a_1 + a_2x + \cdots = (1/x)(A(x)-a_0)$$, so we obtain $$\frac{1}{x^2}(A(x) - a_0 - a_1x) = \frac{3}{x} (A(x)-a_0 ) + A(x).$$

Substituting for $$a_0$$ and $$a_1$$ and solving for $$A(x)$$ yields your $$F(x)$$, ie $$A(x) = \frac{2-5x}{1-3x-x^2}.$$

Now the for the partial fraction decomposition, which is not so ugly if we keep our heads straight. Note that $$1-3x-x^2$$ has roots $$\alpha_1 = -\frac{3}{2} - \frac{\sqrt{13}}{2}$$ and $$\alpha_2 = -\frac{3}{2} + \frac{\sqrt{13}}{2}$$ and we want $$\frac{1}{1-3x-x^2} = \frac{1}{(x-\alpha_1)(x-\alpha_2)} = \frac{A}{(x-\alpha_1)} + \frac{B}{(x-\alpha_2)}.$$ Using this equation and solving for $$A$$ and $$B$$ yields \begin{align} \frac{1}{1-3x-x^2} &= \frac{1}{(\alpha_1-\alpha_2)(x-\alpha_1)} + \frac{1}{(\alpha_2-\alpha_1)(x-\alpha_2)}\\ &=\frac{1}{-\sqrt{13}(x-\alpha_1)} + \frac{1}{\sqrt{13}(x-\alpha_2)} \end{align}

So we have

\begin{align} A(x) &= (2-5x)\left(\frac{1}{-\sqrt{13}(x-\alpha_1)} + \frac{1}{\sqrt{13}(x-\alpha_2)} \right)\\ &=(2-5x) \left( \frac{1}{\alpha_1\sqrt{13}} \cdot \frac{1}{1-(x/\alpha_1)} + \frac{1}{-\alpha_2\sqrt{13}} \cdot \frac{1}{1-(x/\alpha_2)} \right)\\ &= (2-5x) \left( \frac{1}{\alpha_1\sqrt{13}} \sum_{n\ge 0} \left(\frac{1}{\alpha_1} \right)^n x^n + \frac{1}{-\alpha_2\sqrt{13}} \sum_{n\ge 0} \left(\frac{1}{\alpha_2} \right)^n x^n \right)\\ &= \frac{(2-5x)}{\sqrt{13}} \left(\sum_{n\ge 0} \left[ \left(\frac{1}{\alpha_1} \right)^{n+1} - \left(\frac{1}{\alpha_2} \right)^{n+1}\right] x^n \right) \end{align}

Can you take it from here?

• You beat me to it... (+1) Oct 19 '19 at 2:58

By using another method I got the closed-form as follows:

$$a_n = \left( 1 - \frac{2}{\sqrt{13}}\right)\left( \frac{3+\sqrt{13}}{2}\right)^n + \left( 1 + \frac{2}{\sqrt{13}}\right)\left( \frac{3-\sqrt{13}}{2}\right)^n$$

However I need to find $$a_n$$ by using the generating function $$F(x)$$ as described earlier.

The Lucas polynomials are defined by \begin{align} L_{n}(x) = \begin{cases} 2 & n=0 \\ 1 & n=1 \\ x \, L_{n-1}(x) + L_{n-2}(x) & n \geq 2\end{cases}. \end{align} From this it easy to see that $$a_{n} = L_{n}(3)$$.

By the generating function: \begin{align} \sum_{n=0}^{\infty} L_{n+2}(x) \, t^n &= x \, \sum_{n=0}^{\infty} L_{n+1}(x) \, t^n + \sum_{n=0}^{\infty} L_{n}(x) \, t^n \\ \frac{1}{t^2} \, \sum_{n=2}^{\infty} L_{n}(x) \, t^n &= \frac{x}{t} \, \sum_{n=1}^{\infty} L_{n}(x) \, t^n + \sum_{n=0}^{\infty} L_{n}(x) \, t^n \\ \frac{1}{t^2} \, \left(F - L_{0}(x) - L_{1}(x) \, t \right) &= \frac{x}{t} \, (F - L_{0}(x)) + F \hspace{15mm} F = \sum_{n=0}^{\infty} L_{n}(x) \, t^n \\ (1 - x \, t - t^2) \, F &= L_{0}(x) + (L_{1}(x) - x \, L_{0}(x) ) \, t \\ \sum_{n=0}^{\infty} L_{n}(x) \, t^n &= \frac{L_{0}(x) + (L_{1}(x) - x \, L_{0}(x)) \, t}{1- x \, t - t^2} \end{align} This can also be seen as $$\sum_{n=0}^{\infty} L_{n}(x) \, t^n = \frac{2 + (1-2 x) \, t}{1 - x \, t - t^2}.$$ Letting $$x=3$$ gives the desired result.