Contradiction in solving recurrence?

Question

Solve the recurrence $u_n = 2u_{n-1}-u_{n-2}$ if $u_0 = 0$ and $u_1 = 1$.

The characteristic polynomial gives $x^2-2x+1 = 0 \implies x = 1$ and so $u_n = \lambda_1+\lambda_2$. But since $u_0 = 0$, we get $\lambda_1+\lambda_2 = 0 \implies u_n = 0$, a contradiction. What did I do wrong?

Answer 1

Characteristic equation has a root at $x = 1$, so the general solution is $$u_n = 1^n \left[ \lambda_1 + n \lambda_2\right] = \lambda_1 + n \lambda_2$$

Answer 2

The characteristic polynomial has a repeated root $x$ of order $2$ and no other roots. . So $u_n=Anx^n +Bx^n$ for constants $A,B.$ Of course $x=1$ so $u_n=An+B.$ And of course $u_0=0$ and $u_n=1$ gives $A=1,B=0.$

Answer 3

For a low-tech solution, one can rearrange this recurrence relation to the form $u_n-u_{n-1}=u_{n-1}-u_{n-2}$. Since this is valid for all $n\geq 2$, we conclude that $u_n-u_{n-1}$ is independent of $n$, and in particular $u_n-u_{n-1}=u_1-u_0=1$. Hence

$$u_n=(u_n-u_{n-1})+(u_{n-1}-u_{n-2})+\cdots+(u_1-u_0)+u_0 = n.$$