# Contradiction in solving recurrence?

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?

• When there is a repeated root, the solution is not just the pure exponential part. – user296602 Jul 28 '16 at 3:18
• Last time I cheked, $-1$ is not a root of $x^2-2x+1=0$. – Shalop Jul 28 '16 at 3:27

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$$
• @JohnRyan you only capture 1 family of solutions, and use $-1$ instead of $+1$ as the root – gt6989b Jul 28 '16 at 4:04
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.$
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.$$