6
$\begingroup$

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.

2 Answers 2

7

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

  • 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....2012-10-10
  • 0
    @RossMillikan I canceled one $an$, note that there were 2 on LHS and one on RHS ;)2012-10-10
  • 0
    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?2012-10-11
  • 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.2012-10-11
  • 0
    If you have a more general equation of the type $T(n)=aT(n-1)+bT(n-2)+P(n)$, with $a,b$ fixed constants, the same idea works, but sometimes you need to look for a polynomial of degree 1 more or 2 more, depending on if $1$ is a root or a double root of the characteristic equation....2012-10-11
  • 0
    Thanks a lot for the help. Consider some other equation like: F(n) = F(n - 1) + F(n - 2) + 2 * sqrt(3 + F(n-1)*F(n-2)) F(0) = a, F(1) = b It is given that a and b are such that every term in sequence is a integer. Is there any way of applying method of undetermined coefficient here? If not how do we approach this problem.2012-10-12
  • 0
    I don't think you can use that method here... The square root puzzles me, I would try to get rid of it (move everything else on the other side and square)... Then maybe you get lucky and you get a nice recurrence in something like $T(n)^2+cT(n)T(n-1)$ for the appropriate $c$.... But really, I have no idea how to solve this :D2012-10-12
4

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.

  • 0
    @Ross thx, will edit.2012-10-11