Help to understand method to find a solution to a second order linear recurrence

Question

Here's an excerpt from my lecture notes:

Choosing a Particular Solution

$$ ay_{t+2}+by_{t+1}+cy_t=f(t)\,,\qquad t = 0, 1,2,\ldots $$ $$ \begin{array}{|c|c|}\hline f(t)&\text{First choice for Particular Solution}\\ \hline \hline 0&0\\ \hline \text{(Non-Zero constant) }-5&D\\\hline \text{(Linear) }-6t&Dt+E\\\hline\text{(Quadratic) }5t^2-8&Dt^2+Et+F\\\hline -3(5)^t&D(5)^t\\\hline t(6)^t&(Dt+E)(6)^t\\t^2(-3)^t&(Dt^2+Et+F)(-3)^t\\\hline 3\cos(5t)&D\cos(5t)+E\sin(5t)\\4\sin(2t)&D\cos(2t)+E\sin(2t)\\\hline (4)^t\cos(3t)&(4)^t[D\cos(3t)+E\sin(3t)]\\\hline(4)^t\sin(3t)&(4)^t[D\cos(3t)+E\sin(3t)]\\\hline\end{array} $$

I would like to know how the choice of particular solution was deduced (I tried asking my lecturer but she won't tell as it is not in my syllabus).

I know the following:

1. The general solution of a non-homogeneous equation = Particular solution + General Solution of that homogeneous equation.

2. In the case of a homogeneous equation, a constant multiple of its solution is a solution too. Also, the sum of two of its solution is also a solution.

Knowing the above, I still don't know how to deduce the choice of a particular solution. I would appreciate it if someone could explain this to me or direct me to some online reading specifically address this point i.e. second order linear difference equation.

Answer 1

$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,}% \newcommand{\dd}{{\rm d}}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\fermi}{\,{\rm f}}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\half}{{1 \over 2}}% \newcommand{\ic}{{\rm i}}% \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\ol}[1]{\overline{#1}}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{ay_{t + 2} + by_{t + 1} + cy_{t} = \fermi\pars{t}\,,\qquad t = 0, 1,2,\ldots}$

Let's introduce $\ds{{\cal Y}\pars{z} \equiv \sum_{t = 0}^{\infty}y_{t}\,z^{t}}$ and $\ds{{\cal F}\pars{z} \equiv \sum_{t = 0}^{\infty}\fermi\pars{t}\,z^{t}}$. Then, $$ \sum_{t = 0}^{\infty}\pars{ay_{t + 2} + by_{t + 1} + cy_{t}}z^{t} = \sum_{t = 0}^{\infty}\fermi\pars{t}z^{t} \equiv {\cal F}\pars{z} $$ which yields \begin{align} &{\cal F}\pars{z} =a\sum_{t = 2}^{\infty}y_{t}z^{t - 2} + b\sum_{t = 1}^{\infty}y_{t}z^{t - 1} + c\sum_{t = 0}^{\infty}y_{t}z^{t} = {a \over z^{2}}\bracks{{\cal Y}\pars{z} - y_{0} - y_{1}z} + {b \over z}\bracks{{\cal Y}\pars{z} - y_{0}} + c{\cal Y}\pars{z} \\[3mm]&= \pars{{a \over z^{2}} + {b \over z} + c}{\cal Y}\pars{z} - {ay_{0} \over z^{2}} - {by_{0} + ay_{1} \over z} \\[3mm] &z^{2}{\cal F}\pars{z}= \pars{cz^{2} + bz + a}{\cal Y}\pars{z} - ay_{0} - \pars{by_{0} + ay_{1}}z \end{align}

$$ {\cal Y}\pars{z} = {{\cal G}\pars{z}\over cz^{2} + bz + a}\quad\mbox{where}\quad {\cal G}\pars{z} \equiv z^{2}{\cal F}\pars{z} + ay_{0} + \pars{by_{0} + ay_{1}}z $$ Now, we can expand both members of $\ds{{\cal Y}\pars{z} = {{\cal G}\pars{z}\over cz^{2} + bz + a}}$ in powers of $z$. By comparing 'term a term' we can find $y_{t}\,,\ \forall\ t = 0,1,2,\ldots$. Also $$ {\cal Y}\pars{z} = {1 \over c}\,{{\cal G}\pars{z} \over \pars{z - z_{-}}\pars{z - z_{+}}} \quad\mbox{where}\quad z_{\pm} = {-b \pm \root{b^{2} - 4ca} \over 2c} $$ $$ {\cal Y}\pars{z} = {{\cal G}\pars{z} \over c}\,{1 \over z_{+} - z_{-}} \pars{{1 \over z - z_{+}} - {1 \over z - z_{-}}} = {1 \over \root{b^{2} - 4ca}}\bracks{% {1 \over z_{-}}\,{{\cal G}\pars{z} \over 1 - z/z_{-}} - {1 \over z_{+}}\,{{\cal G}\pars{z} \over 1 - z/z_{+}}} $$ In order to proceed further, in general terms, we need additional information of the parameters $\braces{a,b,c}$.

In order to illustrate the general procedure, we'll consider a particular case: $$ a = c = 1\,,\quad b = -2\,,\quad y_{0} = 0\,,\quad y_{1} = 1\,,\quad \fermi\pars{t} \equiv -6t $$ Then $\pars{~\mbox{with}\ \verts{z} < 1~}$, \begin{align} &{\cal F}\pars{z} = \sum_{t = 0}^{\infty}\pars{-6t}z^{t} =-6z\,\totald{}{z}\sum_{t = 0}^{\infty}z^{t} = -6z\,\totald{}{z}\pars{1 \over 1 - z} = -\,{6z \over \pars{1 - z}^{2}} \\[3mm]& \mbox{such that}\ {\cal G}\pars{z} = -\,{6z^{3} \over \pars{1 - z}^{2}} + z = {-6z^{3} + \pars{z - 1}^{2}z \over \pars{1 - z}^{2}} = {-5z^{3} -2z^{2} + z \over \pars{1 - z}^{2}} \\[3mm]& \mbox{and}\ {\cal Y}\pars{z} = {-5z^{3} - 2z^{2} + z \over \pars{1 - z}^{4}} =\pars{-5z^{3} - 2z^{2} + z}\,\sum_{t = 0}d_{t}z^{t} \\[3mm]&\mbox{where}\ d_{t} \equiv {1 \over 6}\pars{t + 1}\pars{t + 2}\pars{t + 3} \end{align} \begin{align} {\cal Y}\pars{t} &= -5\sum_{t = 3}^{\infty}d_{t - 3}z^{t} -2\sum_{t = 2}^{\infty}d_{t - 2}z^{t} + \sum_{t = 1}^{\infty}d_{t - 1}z^{t} \\[3mm]&= d_{0}z + \pars{d_{1} - 2d_{0}}z^{2} + \sum_{t = 3}^{\infty}\pars{d_{t - 1} -2d_{t - 2} - 5d_{t - 3}}z^{t} \\[3mm]&= z + 2z^{2} + \sum_{t = 3}^{\infty}\pars{d_{t - 1} -2d_{t - 2} - 5d_{t - 3}}z^{t} \end{align}

The solution becomes: \begin{align} &y_{0} = 0\,,\quad y_{1} = 1\,,\quad y_{2} = 2\,;\qquad\qquad y_{t} = d_{t - 1} -2d_{t - 2} - 5d_{t - 3}\,,\quad t \geq 3 \\[3mm]&\mbox{where}\ d_{t} \equiv {1 \over 6}\pars{t + 1}\pars{t + 2}\pars{t + 3} \end{align}

Answer 2

The general solution to any homogeneous difference equation is composed of terms $p(n)q^n$ where $p(n)$ is a polynomial in $n$ and $q$ is a, possibly complex, number. All examples in the table are of this form. Try to check this.

So if the right hand side is composed of terms of this form, the general solution of the difference equation is part of the solution set of a difference equation of higher order. That is why it works to make an ansatz of the same form, only setting the coefficients of all polynomial factor as variables.

If one of the $q$ is a solution of the characteristic equation $aq^2+bq+c=0$, then you have to increase the degree of the polynomial factor by one or two. In all other cases, the degree stays the same.