Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
The thing is that what you now have there is an inhomogeneous linear recurrence relation, and those are indeed slightly more tricky to solve than homogeneous ones... –  J. M. Jul 28 '12 at 8:26
    
$S_n = F_n + b(F_n - 1)$ is incorrect. For example with $n=2$, $S_2 = 1 + b$ but $F_2 + b(F_2 - 1) = 1$. –  Cocopuffs Jul 28 '12 at 8:57
    
@Cocopuffs : I forgot to mention that given S(1) = 1 and S(2) = 1 the formula $$S_n = F_n + b(F_n-1)$$ exits –  sabari Jul 28 '12 at 12:00

2 Answers 2

up vote 1 down vote accepted

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$.)

share|improve this answer
    
It works but can you explain why T(n) is specifically S(n) + an + 3a + b ? –  sabari Jul 28 '12 at 13:08
    
See Edit. $ $ $ $ –  Did Jul 28 '12 at 15:19

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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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