Solve $a_n - 4a_{n-1} + 4a_{n-2} = 2^n$

Question

Solve $a_n - 4a_{n-1} + 4a_{n-2} = 2^n$

given that $a_0 = 0$, and $a_1 = 3$

My Attempt:

Get the characteristic equation and solve it. For homogeneous equation

$x^2 -4x + 4 = 0$

$x = 2 $ or $ x = 2$

Hence, $a_n^h = (A+Bn)\cdot2^n $

Guess a particular solution: $n^22^nC$

$n^22^nC - 4(n-1)^22^{n-1}C + 4(n-2)^22^{n-2}C = 2^n$

$n^2C - 2(n-1)^2C + (n-2)^2C = 1$

$C= \frac12$

Hence, $a^p_n = \frac12n^22^n$

$a_n = a^p_n + a^h_n$

$a_n = (A+Bn)\cdot2^n + \frac12n^22^n$

$a_0 = 0 = A$

$a_1 = 3 = 2B + 1$

$B = 1$

Therefore, $a_n = (n+ \frac12n^2)2^n$

Answer 1

No, $n^22^{n^2}C$ does not work. Try with $n^22^{n}C$. Then $$2^n=a_n - 4a_{n-1} + 4a_{n-2} = n^22^{n}C-4(n-1)^22^{n-1}C+4(n-2)^22^{n-2}C=2^{n}\cdot 2C$$ which implies that $C=1/2$.

In general, if the r.h.s. is $r^n$ and $r$ is a solution of the characteristic polynomial of multiplicity $m$, then a particular solution has the form $n^m C r^n$. Note that $n^i r^n$ is a solution of the homogeneous recurrence for $0\leq i<m$.

Answer 2

$\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{a_{n} - 4a_{n - 1} + 4a_{n - 2} = 2^{n}\,;\qquad a_{0} = 0\,,\quad a_{1} = 3}$.

\begin{align} &a_{n} - 4a_{n - 1} + 4a_{n - 2} = 2^{n} \implies 1 = {a_{n} \over 2^{n}} - 2\,{a_{n - 1} \over 2^{n - 1}} + {a_{n - 2} \over 2^{n - 2} } \end{align}

---

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

---

Then, \begin{align} \sum_{n = 0}^{\infty}{a_{n} \over 2^{n}}\,z^{n} & = -\,{z^{2} - 3z \over 2\pars{1 - z}^{3}} = -\,{1 \over 2}\sum_{n = 0}^{\infty}{-3 \choose n}\pars{-1}^{n} \pars{z^{n + 2} - 3z^{n + 1}} \\[5mm] & = -\,{1 \over 4}\sum_{n = 0}^{\infty}\pars{n + 2}\pars{n + 1} \pars{z^{n + 2} - 3z^{n + 1}} \\[5mm] & = -\,{1 \over 4}\sum_{n = 2}^{\infty}n\pars{n - 1}z^{n} + {3 \over 4}\sum_{n = 1}^{\infty}\pars{n + 1}n\,z^{n} \\[5mm] & = {3 \over 2}\,z + \sum_{n = 2}^{\infty} \bracks{-\,{1 \over 4}\,n\pars{n - 1} + {3 \over 4}\,\pars{n + 1}n}\,z^{n} = {3 \over 2}\,z + \sum_{n = 2}^{\infty}{\pars{n + 2}n \over 2}\,z^{n} \\[5mm] & = \sum_{n = 0}^{\infty}{\pars{n + 2}n \over 2}\,z^{n} \implies {a_{n} \over 2^{n}} = {\pars{n + 2}n \over 2} \implies \bbox[10px,#ffe,border:0.1em groove navy]{\color{#f00}{a_{n}} = \color{#f00}{\pars{n + 2}n\,2^{n - 1}}\,,\quad \forall\ n \geq 0} \end{align}