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?

  • 1
    $\begingroup$ $T_{k-1} = k-1$ by the induction hypothesis. $\endgroup$ – JJC94 May 6 '16 at 1:44
  • $\begingroup$ Technically there are two types of induction: simple induction (where you only use the $T_k$ statement to prove the $T_{k+1}$ statement) and strong induction where you assume the statement to be true for $1,2,3,\ldots,k$ to prove it true for $k+1$. For more see this question $\endgroup$ – Winther May 6 '16 at 1:48
  • $\begingroup$ Isn't this what I'm trying to prove? I thought I can't use things that I'm trying to prove $\endgroup$ – Jodo1992 May 6 '16 at 1:49
  • $\begingroup$ @Winther, yes I am using strong induction here. $\endgroup$ – Jodo1992 May 6 '16 at 1:49
  • 2
    $\begingroup$ You are not assuming anything about $T_{k+1}$. You know (the strong induction hypotesis) that $T_n = n$ for $n=1,2,3,\ldots,k$ so in particular it holds for $T_{k-1}$ and $T_k$ $\endgroup$ – Winther May 6 '16 at 1:50

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.