Given the recurrence $T_n = 2T_{n-1} - T_{n-2}$, prove by Induction that $T_n = n$
Note that $T_n = 2T_{n-1}-T_{n-2}$ is equivalent to $T_n -T_{n-1} = T_{n-1}-T_{n-2}$.
Thus $T_n -T_{n-1}$ is constant and equal to $T_1 -T_{0}=1$.
Therefore, $T_n=T_{n-1}+1$ and induction is very easy now.
We have$ T_0 = 0 , T_1 = 1 . $I will prove inductively that$ T_n = n .(1)$
Let $(1) $be true at $n= k .$ Thus ,$ T_{k+1} =2T_k-T_{k-1} = 2k-(k-1) = k+1$ . So $(1)$ is also true at $n = k .$
I have completed the proof :$T_n = n$