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

Question

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

3. We know that $T_k=k$$$T_{k+1}=2(k)-T_{k-1}$$

But where do I go from here? I don't have the value for $T_{k-1}$, so how to I continue?

Answer 1

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.

Answer 2

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$