5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ rot13(Sebz BRVF, gur svefg fvk ahzoref pbeerfcbaq gb frireny frdhraprf eryngrq gb gur Gbjref bs Unabv chmmyr, naq gur ynfg gjb ner irel pybfr gb gur 7gu naq 8gu ahzoref sebz gubfr frdhraprf, ohg abg rknpg.) $\endgroup$ – Thomas Markov Jun 27 at 10:09
4
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.