# Given the recurrence $T_n = 2T_{n-1} - T_{n-2}$, prove by Induction that $T_n = n$

Given the recurrence$$T_n = 2T_{n-1}-T_{n-2},$$$$T_0=0$$$$T_1=1$$Prove by induction, that $T_n = n$.

I have the first few steps worked out.

1. Basis: $n = 1$$T_1=1=n=1$$ 2. Assume true for$n = k+1$$T_{k+1}=2T_k-T_{k-1}$$