\documentclass[11pt]{article}

\usepackage{precalc}

\begin{document}

\assigntitle{23}{Sequences}

\topic{a mysterious rule}
Suppose $n$ is an integer, and consider this simple rule: if $n$ is
even, divide it by two; otherwise, multiply $n$ by $3$, and add one.
Pretty simple, right?  Let's call it Rule $H$.  Written formally,
\begin{equation*}
  H(n) = \begin{cases} n/2  & \text{if $n$ is even,} \\ 
                       3n+1 & \text{otherwise.} 
         \end{cases}
\end{equation*}

\begin{problem}
\topic{easy peasy}
What do you get when you apply Rule $H$ to each of the following integers?
\begin{subproblems}
  \item $10$
  \item $29$
  \item $5$
  \item $1$
  \item $0$
  \item $-5$
\end{subproblems}
\end{problem}

\topic{iteration}
Not all that exciting, huh?  Well, consider applying Rule $H$
repeatedly, instead of just once (this is called \term{iterating} the
rule). For example, if we start with $10$, applying
the rule once gives $5$; applying it again to $5$ gives $16$,
applying it to $16$ gives\dots and so on.

\begin{problem} \label{prob:collatz-10}
  Continue iterating Rule $H$ starting with $10$.  What happens?
\end{problem}

\begin{problem} \label{prob:collatz-misc}
  What happens when you iterate Rule $H$ starting from each of the
  following integers?
  \begin{subproblems}
    \item $3$ \item $6$ \item $7$ \item $9$ \item $15$ \item $27$
      (\emph{Hint:} this one is mean of me, you don't have to do the
      whole thing.  What do you \emph{think} will happen?)
  \end{subproblems}
\end{problem}

\topic{the Collatz conjecture}
As you can see, iterating $H$ leads to some rather unpredictable,
crazy behavior!  It seems like (most? all?) numbers eventually reach
$1$ if you iterate $H$, but some might take a long time to get there.
Will \emph{every} starting number eventually reach $1$ if you iterate
$H$?  Well\dots \emph{no one knows}!!  Most mathematicians think they
will---this is called the \emph{Collatz conjecture}, named after the
German mathematician Lothar Collatz---but no one has been able to
prove it.  (But no one has been able to find a counterexample,
either.)

\section{Sequences}

A list of numbers in a particular order is called a
\term{sequence}. For example, iterating Rule $H$ starting from $11$
yields the sequence \[ 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8,
4, 2, 1, 4, \dots \] When we talk about sequences, we usually mean ones
that follow particular patterns, although a list of random numbers
still technically counts as a sequence.

The numbers in a sequence are called \term{terms}, and we often use
subscript notation to refer to the terms in a sequence: for example,
if $t$ is a sequence, then $t_1$ is the first term in the sequence,
$t_2$ is the second term, and so on.

It can be fun to try to guess the pattern behind a sequence.  Did you
think that computers are far better than humans at anything having to
do with math?  Think again!  Human brains are incredible
pattern-recognizing machines.\footnote{In fact, they're so amazing
  that they tend to notice patterns in places where there actually
  aren't any.  This is why people say that clouds look like llamas (or
  whatever), and why, if you stare at static on a TV screen long
  enough, you will start to see lines and shapes emerging from the
  chaos, and why people claim to see pictures of the Virgin Mary in
  half-eaten grilled cheese sandwiches.}  Computers are great at doing
tedious, repetitive calculations without getting tired or making
mistakes, but they're only good at following instructions; it's very
difficult to reduce pattern recognition to a set of
instructions.\footnote{This is actually an active area of ongoing
  research in artificial intelligence.}

\begin{problem} \label{prob:guess-seq-patterns}
Put your pattern-recognizing machinery to work!  Find the pattern or
rule behind each sequence and write down the next term of
each.
\begin{subproblems}
  \item $1$, $3$, $5$, $7$, $9$, $11$, $\dots$
  \item $3$, $1$, $4$, $1$, $5$, $9$, $2$, $\dots$
  \item $1$, $3$, $7$, $15$, $31$, $63$, $\dots$
  \item $1$, $2$, $4$, $8$, $16$, $14$, $10$, $\dots$
  \label{part:seq-adddigits-double}
  \item $1$, $4$, $3$, $7$, $5$, $10$, $7$, $\dots$
  \item $2$, $6$, $30$, $210$, $\dots$
  \item $1$, $3$, $4$, $7$, $11$, $18$, $29$, $\dots$
  \item $10$, $4$, $6$, $-2$, $8$, $\dots$
  \item $3$, $4$, $7$, $12$, $19$, $28$, $\dots$
  \item $2$, $9$, $64$, $625$, $\dots$
\end{subproblems}
\end{problem}

\section{Recursive and explicit definitions}

\topic{recursive definitions}
The most natural and fundamental way to define a sequence is with a
\term{recursive} definition (also known as a \term{recurrence
  relation}), which uses previous terms to calculate new ones. For
example, \[ t_n = 2\cdot t_{n-1} + 1 \] is a recursive definition
which says that the $n$th term is one more than twice the $(n-1)$st
term.  We also need some sort of \term{base case} that tells us where
to start---one or more terms must be defined without reference to
previous terms.  In this case, we might say $t_1 = 1$.  So we know to
start with $1$, which means the next term is $2 \cdot 1 + 1 = 3$, and
the next after that is $2 \cdot 3 + 1 = 7$, then $15$, and so on.  You
may notice that the all of the ``hailstone sequences'' from
Problems~\ref{prob:collatz-10}--\ref{prob:collatz-misc} are defined
recursively: for example, $t_1 = 10$ and $t_n = H(t_{n-1})$.

\begin{problem}
  Consider the sequence recursively defined by 
  \begin{align*}
    t_1 &= 1 \\ 
    t_n &= (t_{n-1})^2 + 1.
  \end{align*}
  What is $t_5$ (the fifth term in the sequence)?
\end{problem}

\begin{problem} \label{prob:need-two-base-cases}
  Consider the following recursive definition:
  \begin{align*}
    t_1 &= 4 \\
    t_n &= 5 t_{n-2} + 3
  \end{align*}
  What is $t_5$?  How about $t_4$?  What's the problem?  How would
  you fix it?
\end{problem}

\topic{explicit definitions}
Another way to define a sequence is with an \term{explicit}
definition, which describes how to calculate any term using only its
position in the sequence (often denoted $n$).  For example, we might
have $s_n = 2^n - 1$.  This explicit formula says that to get the
$n$th term in the sequence $s$, raise $2$ to the power of $n$ and
then subtract one.  So, if $n$ is $1$, $2$, $3$, $4$, $\dots$ we get
$1$, $3$, $7$, $15$, $\dots$ and so on.

\begin{problem} \label{prob:recursive-vs-explicit}
  As you may have already guessed, the two definitions used as examples above
  actually define the same sequence:
  \begin{align*}
    s_n &= 2^n - 1 \\
\intertext{and}
    t_1 &= 1 \\
    t_n &= 2\cdot t_{n-1} + 1
  \end{align*}
  both define the sequence $1$, $3$, $7$, $15$, $31$, $\dots$, which
  you met in \pref{prob:guess-seq-patterns}.
  \begin{subproblems}
    \item Calculate the twentieth term in the sequence.  Which
    definition did you use?
    \item $72057594037927935$ is a term in the sequence. Calculate the
    terms immediately following and preceding it.  Which definition
    did you use?
  \end{subproblems}
\end{problem}

\begin{problem} \label{prob:equiv-recursive-explicit}
  Let's prove that the sequences $s$ and $t$ in
  \pref{prob:recursive-vs-explicit} are actually the same (I
  \emph{said} they were the same, but you shouldn't just take my word
  for it!).

  We can prove that they are the same by \term{induction}:  if we can
  prove that $t_1 = s_1$, and that whenever $t_{k-1} = s_{k-1}$ then
  $t_k = s_k$ as well, then we have proved that $t_n$ must be equal to
  $s_n$ for all values of $n$ (Since $t_1 = s_1$, we know that $t_2 =
  s_2$; which means that $t_3 = s_3$; which means that $t_4 = s_4$;
  which means\dots). It's like knocking over dominoes, math-style.

  \begin{subproblems}
    \item Show that $t_1 = s_1$.
    \item \emph{Assume} that $t_{k-1} = s_{k-1}$, and show that $t_k =
      s_k$.  (\emph{Hint:} start with the definition of $t_k$, then
      substitute using the assumption, and then simplify\dots)
  \end{subproblems}

\end{problem}

\section{Some special sequences}

\subsection{Arithmetic sequences}
\label{sec:arithmetic-seq}

Any sequence with the following recursive definition is called an
\term{arithmetic}\footnote{For some odd reason, the noun
\emph{arithmetic} (the subject you studied in elementary school)
is pronounced uh-RITH-meh-tic, but the adjective \emph{arithmetic}
(the type of sequence) is pronounced AIR-ith-MEH-tic.  Go figure.}
sequence:
\begin{equation}
  \begin{aligned}
    t_1 &= a \\
    t_n &= t_{n-1} + d
  \end{aligned}
\end{equation}
$a$ and $d$ can be any real numbers; $a$ is the initial term and
$d$ is the \term{common difference}.

\begin{problem} \label{prob:arithmetic-seq}
Explain, in your own words, what an arithmetic sequence is,
  and give an example.  Why is $d$ called the common difference?
\end{problem}

\begin{problem}
What sequence is obtained when $a=7$ and $d= -2$? Write the
  first seven terms.  
\end{problem}

\begin{problem}
  Is $5$, $5$, $5$, $5$, $\dots$ an arithmetic sequence?  Give values
  for $a$ and $d$, or explain why it is not arithmetic.
\end{problem}

\begin{problem}
  Is $1$, $4$, $9$, $16$, $\dots$ an arithmetic sequence?  Give values
  for $a$ and $d$, or explain why it is not arithmetic.
\end{problem}

\begin{problem}
  Consider the arithmetic sequence with first term $a = 4$ and common
  difference $d = 9$.  Find $t_2$, $t_5$, and $t_{193}$.
\end{problem}

\begin{problem}
  Come up with an explicit definition for the $n$th term of an
  arithmetic sequence with initial term $a$ and common difference $d$.
\end{problem}

\subsection{Geometric sequences}
\label{sec:geometric-seq}

Any sequence with the following recursive definition is called a
\term{geometric} sequence:
  \begin{equation}
    \begin{aligned}
      t_1 &= a \\
      t_n &= r \cdot t_{n-1}
    \end{aligned}
  \end{equation}
$a$ is the initial term and $r$ is the \term{common ratio}.

\begin{problem}
  Explain in your own words what a geometric sequence is, and
  give an example.  Why is $r$ called the \emph{common ratio}?
\end{problem}

\begin{problem}
  What sequence is obtained when $a=16$ and $r = 3/2$? Write the
  first seven terms.  
\end{problem}

\begin{problem}
  Consider the geometric sequence with first term $a = 5$ and common
  ratio $r = 2$.  Find $t_2$ and $t_{15}$.
\end{problem}

\subsection{The Fibonacci sequence}
\label{sec:fibonacci}

Consider the sequence defined recursively as follows:
\begin{align*}
  F_0 &= 0 \\
  F_1 &= 1 \\
  F_n &= F_{n-1} + F_{n-2} \qquad \text{when $n \geq 2$.}
\end{align*}
This is known as the \term{Fibonacci sequence}; it is one of the most
famous sequences in all of mathematics.  (Note that the recursive
definition for the Fibonacci numbers specifies \emph{two} base cases,
since in the general case each term is defined as the sum of the
\emph{two previous} terms; you learned why this is necessary in
\pref{prob:need-two-base-cases}.) 

\begin{problem}
  Compute the first fifteen terms of the Fibonacci sequence, beginning
  with $F_0$.
\end{problem}

\begin{problem}
  Add up the first two terms of the Fibonacci sequence, then add up
  the first three terms, then the first four, then five, and so on.
  What do you notice? (\emph{Hint:} try adding one to each of the sums\dots)
\end{problem}

\begin{problem}
  Visit the On-Line Encyclopedia of Integer Sequences (just Google the
  name, you'll find it).  This is one of my favorite websites; it has
  more information than you could ever want to know on more integer
  sequences than you could ever imagine.
  \begin{subproblems}
    \item Search for the Fibonacci sequence by typing the first seven
      or so terms into the search box.  A page should come up with a
      ton of information about the Fibonacci sequence.  You probably
      won't understand all of it, but that's OK; I don't either.  Find
      something interesting that you \emph{do} understand and write
      about it.
    \item Now go to the very bottom of the page and click on
      ``WebCam''. Change ``reload every 20 seconds'' to ``when I say
      so''.  Now click on ``Next sequence'' until you find an
      interesting sequence that you understand (note: even if you
      don't understand all the words in the main definition of the
      sequence, there are often further explanation and examples
      further down on the page).  There may be quite a
      few that are defined in terms of things you don't know; that's
      OK, just keep skipping until you find one that makes
      sense. Write about it.
  \end{subproblems}

\end{problem}

\end{document}