solving a recurrence relation - finding the general solution

Question

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?

Answer 1

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

$\begin{bmatrix}u_{n+1}\\u_{n}\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}\begin{bmatrix}4\\1\end{bmatrix}\\ \begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}1&n\\0&1\end{bmatrix}\begin{bmatrix}1\\3\end{bmatrix}\\ \begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}1+3n\\3\end{bmatrix}\\ \begin{bmatrix}4+3n\\1+3n\end{bmatrix}\\$

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{u_{0} = 1\,,\quad u_{1} = 4}$.

\begin{align} 0 & =\sum_{n = 0}^{\infty}z^{n + 2}\pars{u_{n + 2} -2u_{n + 1} + u_{n}} = \sum_{n = 2}^{\infty}u_{n}z^{n} - 2z\sum_{n = 1}^{\infty}u_{n}z^{n} + z^{2}\sum_{n = 0}^{\infty}u_{n}z^{n} \\[5mm] = &\ \pars{-u_{0} - u_{1}z + \sum_{n = 0}^{\infty}u_{n}z^{n}} - 2z\pars{-u_{0} + \sum_{n = 0}^{\infty}u_{n}z^{n}} + z^{2}\sum_{n = 0}^{\infty}u_{n}z^{n} \\[5mm] = &\ -1 - 2z + \pars{1 - 2z + z^{2}}\sum_{n = 0}^{\infty}u_{n}z^{n} \\[5mm] \implies &\ \sum_{n = 0}^{\infty}u_{n}z^{n} = {2z + 1 \over 1 - 2z + z^{2}} = {3 - 2\pars{1 - z} \over \pars{1 - z}^{2}} = {3 \over \pars{1 - z}^{2}} - {2 \over 1 - z} \end{align}

---

\begin{align} u_{n} & = \bracks{z^{n}}\sum_{k = 0}^{\infty}u_{k}z^{k} = \bracks{z^{n}}\bracks{{3 \over \pars{1 - z}^{2}} - {2 \over 1 - z}} = \bracks{z^{n}}\bracks{3\sum_{k = 0}^{\infty}{-2 \choose k}\pars{-z}^{k} - 2\sum_{k = 0}^{\infty}z^{k}} \\[5mm] = &\ \bracks{z^{n}}\bracks{3\sum_{k = 0}^{\infty}{k + 1 \choose k}z^{k} - 2\sum_{k = 0}^{\infty}z^{k}} = \bracks{z^{n}}\sum_{k = 0}^{\infty}\pars{3k + 1}z^{k}\implies \bbox[15px,#ffe,border:1px dotted navy]{\ds{u_{n} = 3n + 1}} \end{align}

Answer 3

Hint: rearranging the recurrence and iterating shows an easily recognizable arithmetic progression:

$$ u_{n+2}-u_{n+1} = u_{n+1}-u_n = u_n-u_{n-1} = \cdots = u_1-u_0 = 3 $$