2
$\begingroup$

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 2

2

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$

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

  • 0
    @J.M. Slower than linear recurrence equations method.(I don't use linear recurrence eqautions.)2012-07-07