Question: I was just going through some series and came across one which I wasn’t able to solve. The first 8 numbers of the series are:
1,3,7,19,53,153,449,1331,...

Can anyone tell me a mathematical formula for this series?

Answer: 
The sequence satisfies the recurrence relation

> 
>  $a\_{n+1} = 3a\_n - 2F\_{n-1}$  
>   
> 
>  where $F\_n$ is the $n$th Fibonacci number with $F\_0 = 0$ and $F\_1 = 1$.
> 
> 
> 

So the next number in the sequence, for example, is 

> 
>  $a\_9 = 3a\_8 - 2F\_7 = 3\*1331 - 2\*13 = 3967$
> 
> 
>
There's nothing wrong with @hexomino's answer, but it may be worth adding that

> 
>  rather than going via the Fibonacci sequence, there is a single recurrence relation satisfied by the given sequence: $a\_n=4a\_{n-1}-2a\_{n-2}-3a\_{n-3}$. So the next number is $4\times1331-2\times449-3\times153$ giving the same answer 3967 as @hexomino's formula involving the Fibonacci numbers.
> 
> 
> 

Highbrow explanation for why:

> 
>  We'll use the lovely mathematical machinery known as *generating functions*. This means that given our sequence $(a\_n)$ we write $A(z)=\sum a\_nz^n$ (note: all sums here are over $n\geq0$, and we number our sequence elements from 0); now multiplying by $z$ yields $zA(z)=\sum a\_nz^{n+1}=\sum a\_{n-1}z^n$. That is, multiplication by $z$ equals "shifting by one place", with the convention that $a\_{-1}=0$. Now @hexomino tells us to consider $a\_n-3a\_{n-1}$, which corresponds to taking $A(z)-3zA(z)=(1-3z)A(z)$. This equals $\sum (-2f\_{n-2})z^n$ where $(f\_n)$ is the Fibonacci sequence. ... Well, almost: the $n=0$ and/or $n=1$ terms might be wrong because @hexomino's observation only applies for $n\geq2$. It turns out that, if we take $f\_{-2}=f\_{-1}=0$, then we actually have $(1-3z)A(z)=\sum (-2f\_{n-2})z^n+1$.
> 
> 
> 

Now,

> 
>  it's a famous theorem that $F(z)=\sum f\_nz^n=\frac1{1-z-z^2}$. So $\sum (-2f\_{n-2})z^n=\frac{-2z^2}{1-z-z^2}$. And now we're basically done: we have $(1-3z)A(z)=\sum (-2f\_{n-1})z^n+1=\frac{-2z^2}{1-z-z^2}+1=\frac{1-z-3z^2}{1-z-z^2}$ and so $A(z)=\frac{1-z-3z^2}{1-4z+2z^2+3z^3}$. This means that $(1-4z+2z^2+3z^3)A(z)=1-z-3z^2$, so all the "higher" terms in the sequence of its coefficients are zero, which (remembering the stuff above about multiplication by $z$ corresponding to shifting) means that the sequence satisfies the recurrence relation $a\_n-4a\_{n-1}+2a\_{n-2}+3a\_{n-3}=0$, which is what I claimed above.
> 
> 
> 

Note:

> 
>  if all you care about is the recurrence relation itself, you don't need to keep careful track of the low-order terms and all you *really* need to do is to compute $(1-3z)(1-z-z^2)$ and see what its coefficients are.
> 
> 
>