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.

Sum up to nth term of fibonacci sequence for very large n can be calculated in O($\log n$) time using the following approach:

$$A = \begin{bmatrix} 1&1 \\\\1&0\end{bmatrix}^n$$ $$\begin{bmatrix}f(n+1) \\\\ f(n) \end{bmatrix} = A^n \begin{bmatrix}f(1) \\\\ f(0)\end{bmatrix} $$

We can calculate $A^n$ in O($\log n$) time by calculating $A$, $A^2$, $A^4$, $A^8$...

Now I have another sequence

$$ T(n) = T(n - 1) + T(n - 2) - (4n - 13) $$ $$ T(1) = 3 $$ $$ T(2) = 8 $$

I want to calculate its nth term for large n in O($\log n$) time.

share|improve this question

2 Answers 2

up vote 6 down vote accepted

Let $T(n)=S(n)+an+b$, where $a,b$ will be decided later...

Then

$$S(n)+an+b=S(n-1)+an-a+b +S(n-2)+an-2a+b -(4n-13)$$

Thus

$$S(n)=S(n-1)+S(n-2) +an-3a+b -(4n-13) \,.$$

Now, if we can make

$$an-3a+b=4n-13 \,, (*)$$

we get

$$S(n)=S(n-1)+S(n-2) \,,$$

and hence,as in Fibonnaci,

$$\begin{bmatrix}S(n+1) \\\\ S(n) \end{bmatrix} = A^n \begin{bmatrix}S(1) \\\\ S(0)\end{bmatrix}$$

you can now calculate $S(n)$ within $O(\log n)$ time, and to get $T(n)$ you need to add $an+b$, where $a,b$ are calculated from $(*)$.

share|improve this answer
    
Thanks a lot! This was very helpful. –  Aayush Bahuguna Oct 10 '12 at 22:35
2  
It is a well known technique, basically whenever when you have a linear recurrence + extra stuff, you want to add something to $t(n)$ which cancels the extra stuff... This technique is also used in differential equations, I think it is called the method of undetermined coefficients.... –  N. S. Oct 10 '12 at 22:39
    
@RossMillikan I canceled one $an$, note that there were 2 on LHS and one on RHS ;) –  N. S. Oct 10 '12 at 22:55
    
Is the same procedure(comparing coefficients) applies for the sequence having extra stuff which is not linear i.e T(n) = T(n - 1) + T(n - 2) + P(n) where, P(n) is degree d polynomial. Is there any easy method for this kind of equation? –  Aayush Bahuguna Oct 11 '12 at 17:21
1  
@AayushBahuguna If it is $T(n)=T(n-1)+T(n-2)+P(n)$, you can always find a polynomial $Q(n)$ of the same degree as $P$ so that $S_n=T(n)-P(n)$ satisfies the Fibonacci equation. –  N. S. Oct 11 '12 at 20:26

Let $S(n) = T(n) - 4n - 25$, then \begin{align*} S(n) &= T(n) - 4n - 25 \\&= T(n-1) + T(n-2) - 8n - 13 - 25 \\&= S(n-1) + 4n - 4 + 25 + S(n-2) + 4n - 8 + 25 - 8n - 13 - 25 \\&= S(n-1) + S(n-2) \end{align*} So $S(n)$ fulfills the Fibonacci recurrence. Now do as above and calculate $T(n) = S(n) + 4n+25$ afterwards.

share|improve this answer
    
@Ross thx, will edit. –  martini Oct 11 '12 at 8:22

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.