# solving a recurrence relation - finding the general solution

Solve the recurrence relation:

$u_{n+2} = 2u_{n+1}-u_n$

$u_0 = 1$ and $u_1 = 4$

My calculations:

I have calculated that the characteristic equation is: $t^2-2t+1 = 0$ so the roots are $r_1=1$ and $r_2=1$

here is where I am stuck. The answer says that the general solution is: $u_n=(A+Bn)1^n$ But how do I know and come to that conclusion?

• If your objective is to solve recurrence relations, that is just a fact which you should know: a second order homogeneous recurrence with equal characteristic roots $r_1=r_2=r$ has general solution $(A+Bn)r^n$. If you are looking for a proof that this is the case, please make that clear in your question. – David Mar 13 '17 at 22:55

$\begin{bmatrix}u_{n+2}\\u_{n+1}\end{bmatrix} = \begin{bmatrix} 2&-1\\1&0\end{bmatrix}\begin{bmatrix}u_{n+1}\\u_{n}\end{bmatrix}$

$\mathbf u_n = B^n \mathbf u_0$

Unfortunately B is not diagonalizable.

$\lambda^2 - 2\lambda + 1 = 0\\(\lambda-1)^2$

Choose $v_1$ such that $(B-\lambda I)v_1 = 0\\ v_1 = \begin{bmatrix}1\\1\end{bmatrix}$

Choose $v_2$ such that $(B-I)v_2 = v_1$

$v_2 = \begin{bmatrix}1\\0\end{bmatrix}$

$B\begin{bmatrix}1&1\\1&0\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}1&1\\0&1\end{bmatrix}\\ B = \begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}1&1\\0&1\end{bmatrix}\begin{bmatrix}0&1\\1&-1\end{bmatrix}\\ B^n = \begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}1&1\\0&1\end{bmatrix}^n\begin{bmatrix}0&1\\1&-1\end{bmatrix}= \begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}1&n\\0&1\end{bmatrix}\begin{bmatrix}0&1\\1&-1\end{bmatrix}$
