Given : $ T_0 = 0 $ , $T_1 = 1$
Base case :
$T_2 = 5T_1 - 6T_0 = 5 = 3^2 - 2^2$
$T_3 = 5T_2 - 6T_1 = 19 = 3^3 - 2^3$
Assumption :
$T_n = 3^n - 2^n$ & $T_{n-1} = 3^{n-1} - 2^{n-1}$
To prove :
$T_{n+1} = 3^{n+1} - 2^{n+1}$
$T_{n+1} = 5T_n - 6T_{n-1}$
$ = 5(3^n - 2^n) - 6(3^{n-1} - 2^{n-1})$
$ = 5(3^n - 2^n) - 2.3^{n} + 3. 2^{n}$
$ = 3^n(5-2) - 2^n(5-3)$
$ = 3^n.3 - 2^n.2$
$ = 3^{n+1} - 2^{n+1}$
Hence , $T_n = 3^n - 2^n$ is the solution of the given recurrence.
I just wanted to know if my approach is correct or is there any other way to solve it? Thankyou.
Asked
Active
Viewed 1,675 times
1
Johnathan
- 323
-
Lookin' good to me! – Robert Lewis Oct 28 '17 at 20:05
-
1See Wikipedia about solving recurrence relations. You can use a characteristic polynomial. – user236182 Oct 28 '17 at 20:20
-
1Yes this is correct. Your base case could also, maybe more simply, be $T_0=0$, $T_1=1$. – Did Oct 28 '17 at 20:29
-
@Did Your suggestion to start with $T_0$ and $T_1$ is not just a simplification but a correction. An induction using $T_2$ and $T_3$ as the basis proves the result only for $n\geq2$. So the OP's proof would have to be supplemented with checking $T_0$ and $T_1$ in order to cover all relevant values of $n$. – Andreas Blass Oct 29 '17 at 00:08