1
$\begingroup$

I learnt about finding the $n$th Fibonacci number using matrix exponentiation in $\log n$ time. Then I tried finding similar formula for sequences of the form

$S_{n} = S_{n-1} + S_{n-2} + a n + b$

in terms of Fibonacci sequence.
But I could not find expression except for $a = 0$, in which case it is

$S_n = F_n + b(F_n-1)$

Is there an expression for the general case or is there any method to find the $S_n$ in terms of $F_n$, in which case I can calculate $S_n$ in $\log n$ time?

  • 0
    @Cocopuffs : I forgot to mention that given S(1) = 1 and S(2) = 1 the formula $S_n = F_n + b(F_n-1)$ exits2012-07-28

2 Answers 2

1

Let $T_n=S_n+an+3a+b$ for every $n\geqslant0$, then $(S_n)_{n\geqslant0}$ solves the recursion you are interested in if and only if $(T_n)_{n\geqslant0}$ solves the Fibonacci recursion $T_{n+2}=T_{n+1}+T_n$ for every $n\geqslant0$.

The Fibonacci sequence $(F_n)_{n\geqslant0}$ starts from $(F_0,F_1)=(0,1)$, and the shifted Fibonacci sequence $(F_{n+1})_{n\geqslant0}$ starts from $(F_1,F_2)=(1,1)$, hence $T_n=T_0F_{n+1}+(T_1-T_0)F_n$ for every $n\geqslant0$.

Finally, for every $n\geqslant0$, $ S_n=(S_0+3a+b)F_{n+1}+(S_1-S_0+a)F_n-an-3a-b. $

Edit: Here are some explanations on the introduction of $(T_n)_{n\geqslant0}$. Consider the transformation $\Phi:x\to\Phi(x)$ defined on the space of sequences $x=(x_n)_{n\geqslant0}$ by $\Phi(x)_n=x_{n+2}-x_{n+1}-x_n$ for every $n\geqslant0$. Then $\Phi$ is linear and one wants to solve $\Phi(x)=z^{a,b}$ with $z^{a,b}=(z^{a,b}_n)_{n\geqslant0}$ and $z^{a,b}_n=a(n+2)+b$ for every $n\geqslant0$.

The Fibonacci sequence $F=(F_n)_{n\geqslant0}$ and the shifted Fibonacci sequence $G=(F_{n+1})_{n\geqslant0}$ are linearly independent and in the kernel of $\Phi$. Every sequence $x=(x_n)_{n\geqslant0}$ in the kernel of $\Phi$ is determined by $x_0$ and $x_1$ hence the kernel of $\Phi$ is the vector space generated by $F$ and $G$. Furthermore $\Phi(z^{a,b})=z^{-a,a-b}$ hence $\Phi(z^{-a,-a-b})=z^{a,b}$. This shows that every sequence $x$ such that $\Phi(x)=z^{a,b}$ is $x=\alpha F+\beta G+z^{-a,-a-b}$ for some scalar $\alpha$ and $\beta$. (Note that the $n$th term of $x-z^{-a,-a-b}$ is $x_n+an+3a+b$.)

  • 0
    See Edit. $ $ $ $2012-07-28
1

We have the recurrence relation $S_{n}=S_{n-1}+S_{n-2}+an+b$, and we are going to solve it in terms of $S_{0}$, $S_{1}$, $a$ and $b$. Let us assume that we can write $S_{n}$ in the closed form $\alpha_{n}a+\beta_{n}b+\varphi_{n}S_{0}+\psi S_{1}$ Where $\alpha_{n},\beta_{n},\varphi_{n},\psi_{n}$ are all sequences dependent on n. Now, we see that: $S_{n+1}=S_{n}+S_{n-1}+an+b$ $\alpha_{n+1}a+\beta_{n+1}b+\varphi_{n+1}S_{0}+\psi_{n+1}S_{1} = \alpha_{n}a+\beta_{n}b+\varphi_{n}S_{0}+\psi_{n}S_{1} $ $+\alpha_{n-1}a+\beta_{n-1}b+\varphi_{n-1}S_{0}+\psi_{n-1}S_{1}+an+b$ Equating terms in $a,b,S_{0},S_{1}$ we have $\alpha_{n+1}=\alpha_{n}+\alpha_{n-1}+n$ $\beta_{n+1}=\beta_{n}+\beta_{n-1}+1$ $\varphi_{n+1}=\varphi_{n}+\varphi_{n-1}$ $\psi_{n+1}=\psi_{n}+\psi_{n-1}$ We can find the seed values to be as follows:
$\alpha_{0}=\alpha_{1}=0$
$\beta_{0}=\beta_{1}=0$
$\varphi_{0}=1, \varphi_{1}=0$
$\psi_{0}=0, \psi_{1}=1$
Thus, we can readily say that $\varphi_{n}=F_{n-1}$ and $\psi_{n}=F_{n}$. To find $\beta_{n}$, Draw up a table of $\beta_{n}$, $F_{n}$ and their difference. You should notice that their difference grows linearly, and we can hence say that $\beta_{n}=F_{n}+n-3$ for $(n>3)$
I fear this post is already too messy, so I will just say that you can similarly arrive at the fact that $\alpha_{n}$ exceeds the Fibonacci numbers by a cubic function, which can be shown to be $\frac{1}{2}n^{3}-\frac{9}{2}n^{2}+18n-24$.

We can therefore write $S_{n}$ as: $S_{n}=F_{n-1}S_{0}+F_{n}S_{1}+(F_{n}+n-3)b+(F_{n}+\frac{1}{2}n^{3}-\frac{9}{2}n^{2}+18n-24)a$ For $n\ge 3$