# finding a formula for the generating function for a recurring sequence

I have the sequence

$$a_0=0$$, $$a_1=3$$, $$a_2=0$$, $$a_3=23$$,

and

$$a_n=6a_{n-2} + 8a_{n-3} + 3a_{n-4}$$ for $$n\ge 4$$

and I have to find the formula for the generating function $$A(t)=\sum_{n=0}^\infty a_n t^n$$ and find a formula for $$a_n$$.

So far I have found

$$A(t)=(26-18t^3) / (1-6t^2-8t^3-3t^4)$$

but when I use this I get a formula for $$a_n$$ that does not work.

• Note that the leading term in the numerator should not be $26$ ... it should be $3t$. Besides this the auxuillary equation factorises nicely and might be an easier route to a formula for $a_n$. Feb 25 '20 at 0:10

The recurrence relation and initial conditions imply $$A(t)-0 t^0-3 t^1-0 t^2-23 t^3=6t^2 (A(t)-3t^1) + 8t^3 A(t) + 3t^4 A(t).$$ Solving for $$A(t)$$ yields $$A(t)=\frac{3t+5t^3}{1-6t^2-8t^3-3t^4}=\frac{1/2}{1-3 t} - \frac{3/2}{1+t} + \frac{3}{(1+t)^2} - \frac{2}{(1+t)^3},$$ which immediately implies that $$a_n=\frac{1}{2}\cdot 3^n - \frac{3}{2}(-1)^n + 3\binom{n+1}{1}(-1)^n - 2\binom{n+2}{2}(-1)^n=\frac{3^n-(-1)^n (2 n^2 + 1)}{2}.$$