0
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ What is wrong with my method? $\endgroup$ – John Ryan Jul 28 '16 at 3:56
  • $\begingroup$ @JohnRyan you only capture 1 family of solutions, and use $-1$ instead of $+1$ as the root $\endgroup$ – gt6989b Jul 28 '16 at 4:04
  • $\begingroup$ Reference topic: Homogeneous linear difference equations. $\endgroup$ – DanielWainfleet Jul 28 '16 at 23:13
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.