%%% ===============================================
%%% @TeX-file{
%%% title = "Eigenspaces in Recursive Sequences",
%%% version = "Draft",
%%% author = "Ben Galin",
%%% date = "2005/09/05",
%%% filename = "eigen.tex",
%%% copyright = "Copyright 2005 Ben Galin.
%%% All rights reserved. You may
%%% copy for personal use verbatim
%%% copies of this file provided
%%% that you (i) make absolutely no
%%% changes to this file; and (ii)
%%% keep the original copyright."
%%% }
%%% ===============================================
\documentclass{article}
\usepackage{amsmath} % Math notation and environments
\usepackage{bbm} % Real and Natural Set signs
\usepackage{epic} % Graphs
\usepackage{url} % URL in bibliography and in copyright notes
\begin{document}
\bibliographystyle{apalike}
\title{Eigenspaces in Recursive Sequences\thanks{Draft only. All rights reserved \copyright\ 2005. Source code with limited rights can be found at \protect\url{http://www.bens.ws/professional.php}.}}
\author{Ben Galin\thanks{I would especially like to thank Rick Taylor; much of the following is a derivation of his work.}}
\maketitle
One of the areas of study in discrete mathematics deals with sequences, in particular, infinite sequences. An infinite sequence can be defined\footnote{A more rigorous definition of a sequence is given in the appendix.} as a function $f:\mathbbm{Z^*}\to\mathbbm{R}$ that maps a given nonnegative integer ($\mathbbm{Z^*}$) to a corresponding value. The nonnegative integers can be thought of, then, as the position indices of their associated values. More commonly, however, we use the notation $a_k$ rather than $f(k)$ to denote the $k$th element in a sequence.
Occasionally, we are given a recurrence relation between an element in a sequence, $a_k$, and its preceding ones, $a_{k-1},a_{k-2},\ldots,a_{k-i}$, where $i$ is a positive integer and $i0$.
Similar to the previous discussion, define
$\mathbf{G_k}=\left[
\begin{smallmatrix}
G_k \\
G_{k-1}
\end{smallmatrix}
\right]$, for all integers $k\geq 1$. We can represent the sequence in~\eqref{eq:arithmetic} as a system of two equations in a matrix form:
\begin{equation}\nonumber
\begin{bmatrix}
G_k \\
G_{k-1}
\end{bmatrix} =
\begin{bmatrix}
2 & -1 \\
1 & 0
\end{bmatrix}
\begin{bmatrix}
G_{k-1} \\
G_{k-2}
\end{bmatrix} \:.
\end{equation}
Equation~\eqref{eq:system-k} for this case becomes
\begin{equation}\nonumber
\begin{bmatrix}
G_k \\
G_{k-1}
\end{bmatrix} =
\begin{bmatrix}
2 & -1 \\
1 & 0
\end{bmatrix}^{k-1}
\begin{bmatrix}
1 \\
1
\end{bmatrix} \:.
\end{equation}
If we proceed to find the eigenvalues of this system, we find that the characteristic equation, $\lambda^2-2\lambda+1=0$, has only one root $\lambda=1$. This is an example of an eigenvalue with a multiplicity of two. Finding two linearly independent eigenvectors is therefore impossible.
Eigenvector $\mathbf{p}=
\left[
\begin{smallmatrix}
p_1 \\
p_2
\end{smallmatrix}
\right]$
has to satisfy the equation
\begin{align}\nonumber
1\cdot p_1-\lambda\cdot p_2 &= 0 \\ \nonumber
p_1-p_2 &= 0 \:.
\end{align}
Choose $p_1$=1, then $p_2$=1, and $\mathbf{p} =
\left[
\begin{smallmatrix}
1 \\
1
\end{smallmatrix}
\right]$.
Remember from equation~\eqref{eq:second-sequence} that a second, linearly independent sequence that satisfies relation~\eqref{eq:arithmetic} is
\begin{equation}\nonumber
0, \lambda, 2\lambda^2, 3\lambda^3, \ldots \:,
\end{equation}
which in the case of $\lambda=1$ becomes
\begin{equation}\nonumber
0, 1, 2, 3, \ldots \:.
\end{equation}
Furthermore, we showed that any linear combination of the sequences
\begin{equation}\label{eq:arithmetic-combo}
\left\{
\begin{split}
1,1,1,1, \ldots \\
0,1,2,3, \ldots
\end{split}
\right.
\end{equation}
also satisfies relation~\eqref{eq:arithmetic}.
Note that any arithmetic sequence can be written as linear combinations of the above sequences. If $a_k=a_{k-1}+c$ for integers $k\geq1$ and $a_0=d$, then $a_k=c\cdot k+d\cdot 1$, or the second sequence in~\eqref{eq:arithmetic-combo} multiplied by $c$ added to the first sequence multiplied by $d$. Therefore, we have shown that any arithmetic sequence satisfies the recurrence relation given in~\eqref{eq:arithmetic}.
\end{document}
of 2-tuples where each tuple takes the form ${i, {i,a}}; i\in \mathbbm{N}, a\in \mathbbm{R} (or \mathbbm{C})$ and where if. Thus a function $f:\mathbbm{N}\to\mathbbm{R}$ can be constructed