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$