How can i find closed-form expressoin of this recursive relation?

Question

Using generating functions, find closed-form expression of this recursive relation:

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

Any hints how to figure out the expression?

Answer 1

Hint Look at the generating function of the sequence $(a_n)$:

$$G(t)=\sum_{n=0}^{\infty} a_n t^n = 1 + t + \sum_{n=2}^{\infty} 3a_{n-1}t^n+\sum_{n=2}^{\infty} 2a_{n-2}t^n = 1 + t + t \sum_{n=1}^{\infty}3a_nt^n + t^2 \sum_{n=0}^{\infty} 2a_n t^n$$

Then $$G(t)=1+t+3t(G(t)-1)+2t^2 G(t)=1-2t+3tG(t)+2t^2G(t)$$

Finally you find $$G(t)=\dfrac{2t-1}{2t^2+3t-1}$$

Now that you have the generating function, can you deduce $a_n$?

Answer 2

Alternative method

Here's an alternative method that uses the auxiliary equation of the recurrence sequence.

First we solve the auxiliary equation as follows.

$r^2-3r-2=0$, so

$r= \frac{3 \pm \sqrt{17}}{2}$.

Thus, the closed form can be written as

$a_n=A(\frac{3 + \sqrt{17}}{2})^n+ B(\frac{3 - \sqrt{17}}{2})^n$

where $A$ and B are constants.

We can find $A$ and $B$ by using the values of the initial terms. $ $ That is, $a_0=1$ and $a_1=1$.
This gives

$1=A(\frac{3 + \sqrt{17}}{2})+ B(\frac{3 - \sqrt{17}}{2})$

$1=A(\frac{3 + \sqrt{17}}{2})^0 + B(\frac{3 - \sqrt{17}}{2})^0=A+B.$

Solving this system gives

$A=\frac{\sqrt{17}-1}{2\sqrt{17}}$ $ $ and $ $ $ B=\frac{1 + \sqrt{17}}{2\sqrt{17}}$.

Hence

$a_n=(\frac{\sqrt{17}-1}{2\sqrt{17}})(\frac{3 + \sqrt{17}}{2})^n+ (\frac{1 + \sqrt{17}}{2\sqrt{17}}) (\frac{3 - \sqrt{17}}{2})^n$.