# What's $T\left(n\right)$?

If $T\left( n \right) = 8T\left( n-1 \right) - 15T\left( n-2 \right); T\left(1\right) = 1; T\left( 2 \right) = 4$,

What's $T\left(n\right)$ ?

I use this method:

Let $c(T(n) - aT(n-1)) = T(n-1) - aT(n-2)$

from $T(n) = 8T(n-1) - 15T(n-2)$, we can get $\begin{cases}c = \frac{1}{3}\\a = 5\end{cases}$ and $\begin{cases}c = \frac{1}{5}\\a = 3\end{cases}$,

then, we get $\frac{T(n)-5T(n-1)}{T(n-1)-5T(n-2)} = 3$,

so, we reach the answer: $T(n) = \frac{3^{n-1}+5^{n-1}}{2}$.

Sorry for my poor English.

-

## 2 Answers

This is second order recurrence equation. Since $T(n)=8T(n-1)-15T(n-2)$, we first solve the quadratic equation: $x^2=8x-15$. Its roots are $3$ and $5$. Therefore, $T(n)$ must be in the form: $$T(n)=a\cdot 3^n+b\cdot 5^n, n\geq 1$$for some constants $a$ and $b$. To find $a$ and $b$, since $1=T(1)=3a+5b$ and $4=T(2)=9a+25b$, we get $a=1/6$ and $b=1/10$, i.e. $$T(n)=\frac{1}{6}\cdot 3^n+\frac{1}{10}\cdot 5^n, n\geq 1$$

-

There is a standard method to solve linear recurrence equations (2x2 matrix) or here.

The solution here is $\displaystyle T(n)=\frac{3^{n-1}+5^{n-1}}2$.

-
Thanks, I use equation to solve it, but much slower :) –  hbc Jul 7 '12 at 9:54
@hbc: solving for the roots of $x^2-8x+15$ is slow? –  Ｊ. Ｍ. Jul 7 '12 at 9:55
@J.M. Slower than linear recurrence equations method.(I don't use linear recurrence eqautions.) –  hbc Jul 7 '12 at 10:06