\documentclass [11pt,letterpaper]{article}


\usepackage{amsmath,amssymb,amsthm,amsfonts}
%\usepackage{times}
\usepackage{enumerate}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{pgf}
\usepackage{url}
\usepackage{subfig}
\usepackage[top=1in,bottom=1in,left=1in,right=1in]{geometry}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}

% New environments
\theoremstyle{definition}
\newtheorem{example}{Example}
\newtheorem{definition}{Definition}
\newtheorem{remark}{Remark}

\newcommand\im{\textup{Im\,}}
\newcommand\re{\textup{Re\,}}
\newcommand\prsp{(\Omega, \mathcal F, \mathbf P)}
\newcommand\pr{\mathbf P}
\newcommand{\fej}[1]{\noindent\textsc{#1}}
\newcommand{\FF}{\mathcal{F}}
\newcommand{\E}{\mathbb{E}}

\begin{document}


\noindent \textbf{\Large Linear Difference Equations}

\noindent Posted for Math 635, Spring 2012.
 
\vspace{.2in}



Consider the following second-order linear difference equation
\begin{equation}
  f(n) = af(n-1) + bf(n+1), \quad  K< n < N,
  \label{eq:difference_gen}
\end{equation}
where $f(n)$ is a function defined on the integers $K \le n \le N$,
the value $N$ can be chosen to be infinity, and $a$ and $b$ are nonzero real
numbers. Note that if $f$ satisfies \eqref{eq:difference_gen} and if
the values $f(K)$, $f(K+1)$ are known then $f(n)$ can be determined
for all $K \le n \le N$ recursively via the formula
\begin{equation*}
  f(n+1) = \frac{1}{b}\big[ f(n) - af(n-1) \big].
\end{equation*}
Note also that if $f_1$ and $f_2$ are two solutions of \eqref{eq:difference_gen}, then $c_1f_1 +
c_2f_2$ is a solution for any real numbers $c_1,c_2$. Therefore,  the solution space of \eqref{eq:difference_gen}
is a two-dimensional vector space and one basis for the space is
$\{f_1,f_2\}$ with $f_1(K) = 1, f_1(K+1) = 0$ and $f_2(K) = 0,
f_2(K+1) = 1$.



We will  solve \eqref{eq:difference_gen} by looking for solutions
of the form $f(n) = \alpha^n$, for some $\alpha \ne 0$.  Plugging $\alpha^n$ into equation \eqref{eq:difference_gen} yields
\begin{equation*}
  \alpha^n = a\alpha^{n-1} + b\alpha^{n+1}, \quad K<n<N,
\end{equation*}
or
\begin{equation*}
  \alpha = a + b\alpha^2 \quad \iff \quad b\alpha^2 - \alpha  + a = 0.
\end{equation*}
Solving this quadratic gives
\begin{equation}
  \alpha = \frac{1 \pm \sqrt{1 - 4ba}}{2b}.
  \label{eq:gen_diff}
\end{equation}

There are two cases that need handling based upon whether or not the discriminant, $1-4ba$, is zero.  \vspace{.1in}

\noindent \textbf{Case 1:}  If $1 - 4ba \ne0$, we find two solutions,
$\alpha_1$ and $\alpha_2$, and see that the general solution to the
difference equation \eqref{eq:difference_gen} is
\begin{equation*}
  c_1 \alpha_1^n + c_2 \alpha_2^{n},
\end{equation*}
with $c_1,c_2$ found depending upon the boundary conditions.
If $1 - 4ba<0$, then the roots are complex and the general solution is found by switching to polar coordinates.  That is, we let $\alpha = re^{i\theta}$, and find
\begin{equation*}
	f(n) = r^n e^{in\theta} = r^n \cos(n\theta) \pm i r^n  \sin(n\theta),
\end{equation*}
are solutions, implying both the real and imaginary parts are solutions.  Therefore, the general solution is
\begin{equation*}
	c_1 r^n \cos(n\theta) + c_2 r^n \sin(n\theta),
\end{equation*}
with $c_1,c_2$ found depending upon the boundary conditions. 



\vspace{.1in}

\noindent \textbf{Case 2:} If $1 - 4ba=0$, we only find the one
solution, $f_1(n) = (1/2b)^n$ by solving the quadratic.  However, let
$f_2(n) = n(2b)^{-n}$.  We have that
\begin{align*}
  af_2(n-1) + bf_2(n+1) &= a(n-1)(2b)^{-(n-1)} + b(n+1) (2b)^{-(n+1)}\\
  &= \left( \frac{1}{2b}\right)^n \left[ a(n-1)2b + b(n+1)\frac{1}{2b}\right]\\
  &=  \left( \frac{1}{2b}\right)^n \left[ (n-1)\frac{1}{2} + (n+1)\frac{1}{2}\right] \qquad \text{(remember, $4ab = 1$)}\\
  &=   \left( \frac{1}{2b}\right)^n n\\
  &= f_2(n).
\end{align*}
Note that $f_2$ is obviously linearly independent from $f_1$.  Thus,
when $4ab = 1$,  the general form of the solution is
\begin{equation*}
  f(n) = c_1\left( \frac{1}{2b}\right)^n + c_2 n \left( \frac{1}{2b}\right)^n. 
\end{equation*} 
with $c_1,c_2$ found depending upon the boundary conditions.

\begin{example}
	Find a function $f(n)$ satisfying
	\begin{equation*}
		f(n) = 2f(n-1) + \frac{1}{10} f(n + 1), \qquad 0<n<\infty,
	\end{equation*}
	with $f(0) = 8, f(1) = 2$. 
	\vspace{.1in}
	
	\noindent \textbf{Solution.}  Here, $a = 2$ and $b = 1/10$.  Therefore, plugging into \eqref{eq:gen_diff} gives
	\begin{equation*}
		\alpha  = 5 \pm \sqrt{5},
	\end{equation*}
	and the general solution is
	\begin{equation*}
		f(n) = c_1\left(5 + \sqrt{5}\right)^n + c_2\left(5 - \sqrt{5}\right)^n.
	\end{equation*}
	Using the boundary conditions yields
	\begin{align*}
		8 &= f(0) = c_1 + c_2\\
		2 &= f(1) = c_1(5 + \sqrt{5}) + c_2(5 - \sqrt{5}),
	\end{align*}
	which has solution $c_1 = 4 - 19\sqrt{5}/5$, $c_2 = 4 + 19\sqrt{5}/5$.  Thus, the solution to the problem is
	\begin{equation*}
		f(n) = \left(4 - \frac{19\sqrt{5}}{5}\right) \left(5 + \sqrt{5}\right)^n + \left(4 + \frac{19\sqrt{5}}{5}\right)\left(5 - \sqrt{5}\right)^n.
	\end{equation*} \hfill $\square$
\end{example}

Some of the most important difference equations we will see in this course
are those of the form
\begin{equation*}
  f(n) = pf(n-1) + qf(n+1), \quad \text{with } p+q = 1, \quad p,q\ge 0.
\end{equation*}
These will arise when studying random walks with $p$ and $q$ interpreted as the associated probabilities of moving right or left.  Supposing that $p \ne q$, the roots of the quadratic formula \eqref{eq:gen_diff} can be found:
\begin{align*}
	\frac{1 \pm \sqrt{1 - 4(1-p)p}}{2q}  = \frac{1 \pm \sqrt{(1-2p)^2}}{2q} = \frac{1 \pm |q - p|}{2q} =  \left\{1,\frac{p}{q}\right\}.
\end{align*}
Thus, the general solution when $p \ne 1/2$ is
\begin{equation*}
  f(n) = c_1 + c_2\left( \frac{p}{q} \right)^n.
\end{equation*}
For the case that $p = q = 1/2$, the only root is 1, hence the general
solution is
\begin{equation*}
  f(n) = c_1 + c_2n.
\end{equation*}

We analyzed only second-order linear difference equations above.  However, and similar to the study of differential equations, higher order difference equations can be studied in the same manner.  Consider the general $k$th order, homogeneous linear difference equation:
\begin{equation}
  f(n+k) = a_0f(n) + a_1f(n+1) + \cdots + a_{k-1}f(n+k-1),
  \label{general_difference}
\end{equation}
where we are given $f(0), f(1), \dots, f(k-1)$.  Then, again, we may solve for the general $f(n)$ recursively using \eqref{general_difference}.  We look for solutions of the form $f(n) = \alpha^n$, which is a solution if and only if
\begin{equation*}
	\alpha^k = a_0 + a_1 \alpha + \cdots + a_{k-1}\alpha^{k-1}.
\end{equation*}
If there are $k$ distinct roots of the above equation, then we automatically get $k$ linearly independent solutions to \eqref{general_difference}.  However, if a given root $\alpha$ is a root with a multiplicity of $j$, then 
\begin{equation*}
	\alpha^n, n\alpha^n, \dots, n^{j-1}\alpha^n,
\end{equation*}
are linearly independent solutions.  We can then use the given initial conditions to find the desired particular solution.



\end{document}
