\documentclass[11pt]{article}
\begin{document}
%%%%% written in LaTeX %%%
\addtolength{\oddsidemargin}{-1.25cm}
\addtolength{\textwidth}{3cm}
\addtolength{\textheight}{4cm}
\addtolength{\topmargin}{-2cm}
\newcommand{\een}{\end{enumerate}}
\newcommand{\noi}{\noindent}
\newcommand{\ra}{\rightarrow}
\newcommand{\sig}{\sigma}
\newcommand{\eps}{\epsilon}
\newcommand{\del}{\delta}
\newcommand{\Del}{\Delta}
\newcommand{\TREE}{\mbox{TREE}}
\newcommand{\lam}{\lambda}
\newcommand{\ah}{\alpha}
\newcommand{\gam}{\gamma}
\newcommand{\ul}{\underline}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bec}{\begin{center}}
\newcommand{\ece}{\end{center}}
\newcommand{\hsa}{\hspace*{1cm}}
\newcommand{\hsb}{\hspace*{2cm}}
\newcommand{\lefta}{\leftarrow}
\newtheorem{conjecture}{Conjecture}
\newtheorem{definition}{Definition}
\newtheorem{define}{Definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{claim}{Claim}[theorem]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{guess}[theorem]{Conjecture}
\bec {\Large\bf LINEAR RECURRANCES} \ece
For a field $F$ let $SEQ[F]$ denote the set of
sequences $\vec{u}=u_0,u_1,u_2,\ldots$ with all
$u_i\in F$. We may add sequences coordinatewise
and multiply by constants and $SEQ[F]$ may profitably
be regarded as a vector space over $F$.
A {\em linear recurrance} of order $k$ is an equation of the form
\beq\label{lr}
u_n = a_1u_{n-1}+\ldots+a_ku_{n-k} \mbox{ for ALL } n\geq k
\eeq
where $a_k\neq 0$. The most famous of these is the Fibonacci
recurrance
\beq\label{fib}
f_n = f_{n-1}+f_{n-1} \mbox{ for ALL } n\geq 2
\eeq
We shall let $SOL$ denote the set of solutions to a given
linear recurrance.
\begin{claim} $SOL$ is a vector space of dimension $k$.
\end{claim}
\noi {\tt Proof:} If $\vec{u},\vec{v}\in SOL$ then we
manipulate terms to get
\[ u_n+v_n = \sum_{i=1}^k a_i (u_{n-i}+v_{n-i}) \]
so $\vec{u}+\vec{v}\in SOL$. Multiplication by a constant
is even simpler. A sequence in $SOL$ is uniquely determined
by its {\em initial values} $u_0,\ldots,u_{k-1}$ so the map
from $SOL$ to $F^k$ given by taking the first $k$ coordinates
is a bijection and so preserves dimension.
For the Fibonacci recursion here are the starts of two solutions and their sum:
\vspace{.1in}
\begin{center}
\begin{tabular}{rrrrrrrr}
0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 \\
1 & 3 & 4 & 7 & 11 & 18 & 29 & 47 \\
1 & 4 & 5 & 9 & 14 & 23 & 37 & 60
\end{tabular}
\end{center}
\vspace{.1in}
The first is {\em the} Fibonacci Sequence, the second is called the
Lucas Sequence. Note their sum also satisfies (\ref{fib}).
The key to studying Linear Recurrances is to look for exponential
solutions. For recurrance (\ref{lr}) we call
\beq \label{char}
p(\ah) = \ah^k-\sum_{i=1}^k a_i\ah^{k-i}
\eeq
the {\em characteristic equation}.
\begin{claim} If $p(\ah)=0$ then $u_n=\ah^n$ satisfies (\ref{lr})
\end{claim}
\noi We simply plug in
\[ u_n=\ah^n=\ah^{n-k}\ah^k = \ah^{n-k}\sum_{i=1}^k a_k\ah^{k-i}
=
\sum_{i=1}^k a_k\ah^{n-i}
= \sum_{i=1}^k a_ku_{n-i}
\]
So every root of the equation $p(x)=0$ [note that as $a_k\neq 0$,
zero is not a root] gives a solution to (\ref{lr}). Now we have
a strong general result about their independence.
\begin{theorem}\label{inde} Let $\ah_1,\ldots,\ah_k$ be distinct nonzero
elements of $F$. Then the sequences $\vec{u}_i = \ah_i^n$ are
linearly independent. That is, there do not exist $c_1,\ldots,c_k$,
not all zero, such that
\beq \label{bad} \sum_{i=1}^k c_i\ah_i^n = 0 \mbox{ for all } n\geq 0
\eeq
\end{theorem}
\noi {\tt Proof:} Suppose (\ref{bad}) held with all $c_i\neq 0$.
Replacing $n$ by $n+1$
\beq \label{bad1} \sum_{i=1}^k c_i\ah_i^{n+1} =
\sum_{i=1}^k c_i\ah_i \ah_i^n=0 \mbox{ for all } n\geq 0
\eeq
Subtracting $\ah_1$ times (\ref{bad}) from (\ref{bad1}), the
$\ah_1^n$ terms cancel and we would
get a smaller dependence
\beq \label{bad2}
\sum_{i=2}^k c_i(\ah_i-\ah_1)\ah_i^n = 0 \mbox{ for all } n\geq 0
\eeq
Continuing in this way (or, formally, via induction) we would get
some $K\ah_k^n=0$, a contradiction.
\noi {\tt Comment:} When $F=Re$ and the $\ah_i$ are positive reals
the theorem can also be derived from asymptotic considerations as the
$\ah_i^n$ with the largest $\ah_i$ dominate as $n\ra\infty$.
\begin{theorem} Suppose $\ah_1,\ldots,\ah_k\in F$ are distinct nonzero
solutions to the characteristic equation (\ref{char}). Then
\beq\label{gen} u_n = \sum_{i=1}^k c_i\ah_i^n \eeq
is the general solution to the recursion (\ref{lr}).
\end{theorem}
\noi {\tt Proof:} The $\ah_i^n$ are solutions, they are linearly
independent, so they span a space of dimension $k$ which is the
dimension of $SOL$ so it must be all of $SOL$.
\noi For Fibonacci (\ref{fib}), $\ah^2=\ah+1$ has the two solutions
\[ \ah_1 = \frac{1+\sqrt{5}}{2},
\ah_2 = \frac{1-\sqrt{5}}{2} \]
so the general solutions is
\beq \label{fibgen} u_n = c_1\ah_1^n + c_2\ah_2^n \eeq
For the given initial conditions $u_0=0,u_1=1$ we use linear
algebra to determine the coefficients $c_1,c_2$:
\[ 0 = c_1\ah_1^0 + c_2\ah_2^0 = c_1 + c_2 \]
\[ 1 = c_1\ah_1^1 + c_2\ah_2^1 = c_1(\ah_1-\ah_2) \]
giving the solution $c_1 = 5^{-1/2}$, $c_2= -c_1$ and the well known
formula:
\beq \label{fibform}
f_n = \frac{1}{\sqrt{5}}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^n
-\left(\frac{1-\sqrt{5}}{2} \right)^n \right]
\eeq
\noi Suppose we had considered Fibonacci (\ref{fib}) over $Q$. Then
$p(x)=x^2-x-1$ would have been irreducible. Instead, we extend $Q$
and now $p$ factors. [Multiple roots still present a problem, more
on that later.] Extending $Q$ to $C$ any polynomial will factor.
So the above method works for any recursion with, say, rational
coefficients by extending to $C$, unless one has multiple roots.
How about linear recurances modulo $p$.
Here is Fibonacci with
$p=11$
\beq\label{fib11} \ul{0},\ul{1},1,2,3,5,8,2,10,1,\ul{0},\ul{1} \ldots
\eeq
and, as the $0,1$ has repeated, we are periodic with period $10$.
Here is Fibonacci with
$p=3$
\beq\label{fib3} \ul{0},\ul{1},1,2,0,2,2,1,\ul{0},\ul{1} \ldots
\eeq
and, as the $0,1$ has repeated, we are periodic with period $8$.
What's going on?
We consider Fibonacci (\ref{fib}) (or {\em any} recursion (\ref{lr})
with integer coefficients over the field $Z_p$.
\noi {\tt Case I:} The characteristic equation $p(x)=0$ splits
completely in $Z_p$ (sorry, different uses of $p$ here) with distinct
roots. Then everything goes through. When, for example, $p=11$,
$x^2-x-1=0$ has roots $\ah_1=8, \ah_2=4$ (one way is to plug in
$\sqrt{5}=\sqrt{16}=4$) and
\beq \label{fib11sol} f_n = 3\cdot 8^n + 8\cdot 4^n \eeq
Periodicity also follows. As all $\ah^{p-1}=1$ we have
$u_{n+(p-1)}=u_n$ whenever we are in Case I. The period can
be smaller than $p-1$ but from this we can deduce that the period
must divide $p-1$.
\noi {\tt Case II:} Not Case I and the characteristic equation
$p(x)=0$ has no multiple roots in any extension of $Z_p$. In
this case we extend $Z_p$ to the splitting field $F$ of $p(x)$
which will be some finite field, $|F|=p^r$. Then everything goes
through. When, for example, $p=3$ we extend to $F=Z_3(\sqrt{2})$
(or, identically, $Z_3[y]/(y^2+1)$) and
\beq \label{fib3sol} f_n = 2\sqrt{2}(2+2\sqrt{2})^n - 2\sqrt{2}
(2-2\sqrt{2})^n \eeq
Periodicity also follows. As all $\ah^{p^r-1}=1$ we have
$u_{n+(p^r-1)}=u_n$ whenever we are in Case II. The period can
be smaller than $p^r-1$ but from this we can deduce that the period
must divide $p^r-1$. Fibonacci even works for $p=2$, though we can't
divide by $2$. We set $GF(4)=\{0,1,y,y+1\}$ with $y^2=y+1$ so
that $p(x)=x^2+x+1$ has roots $y,y+1$ and
\beq \label{fib2sol} f_n = \cdot y^n + \cdot (y+1)^n \eeq
and the period divides $3$ and so it is $3$. Indeed $0,1,1$
repeats.
\noi {\tt Case III:} The characteristic equation $p(x)=0$ has
multiple roots. For Fibonacci this occurs over $Z_p$ only when
$p=5$. At $p=5$, $x^2-x-1 = (x+2)^2$. Why is $p=5$
the {\em only} prime for which this happens? Over $Q[x]$,
$\gcd(p(x),p'(x))= \gcd(x^2-x-1,2x-1)=1$. This implies there
are $a(x),b(x)\in Q[x]$ with
$(x^2-x-1)a(x) +(2x-1)b(x)=1$. Some work
gives
\beq \label{a1} 1 = \frac{1}{5}\left[ (2x-1)(2x-1) - 4(x^2-x-1)
\right] \eeq
Equation (\ref{a1}) applies in any $Z_p$ except $p=5$, as for
all other $p$ one may divide by $5$. In general if $p(x)\in Z[x]$ has
no multiple roots in $Q[x]$ we can find $a(x),b(x)\in Q[x]$ with
$a(x)p(x)+b(x)p'(x)=1$ and this equation will hold in $Z_p$ for
all but the finite number of primes in the denominators of the
coefficients of $a(x),b(x)$.
\begin{claim}
When $p(x)=0$ has a root $\ah$ of multiplicity $m$
the $\ah^nn^i$, $0\leq i < m$ satisfy the linear recursion (\ref{lr}).
\end{claim}
We give the argument only for $m=2$, doubleroots. As $p(\ah)=0$
\beq\label{d1}
\ah^k=\sum_{i=1}^k a_i\ah^{k-i}
\eeq
but now also $p'(\ah)=0$ so that
\beq\label{d2}
k\ah^k=\sum_{i=1}^k (k-i)a_i\ah^{k-i}
\eeq
We already know $u_n=\ah^n$. Now set $u_n=n\ah^n$. We
want
\beq\label{d3}
n\ah^n=\sum_{i=1}^k (n-i)a_i\ah^{k-i}
\eeq
and this is $n-k$ times (\ref{d1}) plus (\ref{d2}).
Does this give all the solutions to the linear recurrance (\ref{lr}). Sometimes!
\begin{theorem}
Assume $F$ has characteristic zero and let $\ah_1,\ldots,\ah_r$ be distinct nonzero
elements of $r$. Let $s_1(x),\ldots,s_r(x)\in F[x]$, not all zero. Then we cannot
have
\beq\label{dd1} \sum_{i=1}^r s_i(n)\ah_i^n = 0 \mbox{ for all } n\geq 0 \eeq
\end{theorem}
\noi As with the proof of Theorem \ref{inde} we plug $n+1$ in for $n$ in (\ref{dd1}) giving
\beq\label{dd2} \sum_{i=1}^r s_i(n+1)\ah_i\ah_i^n = 0 \mbox{ for all } n\geq 0 \eeq
Now subtracting $\ah_1$ times (\ref{dd1}) gives
\beq\label{dd3} \ah_1[s_1(n+1)-s_1(n)]\ah_1^n +
\sum_{i=2}^r t_i(n)\ah_i^n = 0 \mbox{ for all } n\geq 0 \eeq
where $t_i(n)$ has the same degree as $s_i(n)$ for $i\geq 2$ but the coefficient
of $\ah_1^n$ has degree one less. The formal proof is then by induction on the
sum of the degrees.
\begin{theorem} If $F$ has characteristic zero and the characterstic equation
(\ref{char}) has roots $\ah_1,\ldots,\ah_r$ with multiplicities $m_1,\ldots,m_r$
the the general solution to the linear recurrance (\ref{lr}) is
\beq\label{final}
u_n = \sum_{i=1}^r\sum_{j=0}^{m_i-1} c_{ij}n^j\ah_i^n \eeq
\end{theorem}
\end{document}