\documentclass[12pt]{amsart}

\newcommand{\C}{{\mathbf C}}
\newcommand{\Q}{{\mathbf Q}}
\newcommand{\Qbar}{\overline{\Q}}
\newcommand{\kbar}{{\overline{k}}}
\newcommand{\ksep}{{k^{\operatorname{sep}}}}
\newcommand{\kvsep}{{k_v^{\operatorname{sep}}}}
\newcommand{\ksepstar}{{k^{\operatorname{sep} \ast}}}
\newcommand{\kvsepstar}{{k_v^{\operatorname{sep} \ast}}}
\newcommand{\Fbar}{{\overline{\F}}}
\newcommand{\Z}{{\mathbf Z}}
\newcommand{\R}{{\mathbf R}}
\newcommand{\PP}{{\mathbf P}}
\newcommand{\F}{{\mathbf F}}
\newcommand{\tors}{_{\operatorname{tors}}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\Aut}{\operatorname{Aut}}
\newcommand{\Gal}{\operatorname{Gal}}
\newcommand{\Norm}{\operatorname{Norm}}
\newcommand{\Br}{\operatorname{Br}}
\newcommand{\Sel}{\operatorname{Sel}}
\newcommand{\Cl}{\operatorname{Cl}}
\newcommand{\divv}{\operatorname{div}}
\newcommand{\ord}{\operatorname{ord}}
\newcommand{\Div}{\operatorname{Div}}
\newcommand{\Pic}{\operatorname{Pic}}
\newcommand{\Spec}{\operatorname{Spec}}
\newcommand{\GalQ}{{\Gal}(\Qbar/\Q)}
\newcommand{\defequal}{\stackrel{\text{def}}{=}}
\newcommand{\nichts}{{\left.\right.}}
\newcommand{\isom}{\cong}
\newcommand{\tensor}{\otimes}
\newcommand{\directsum}{\oplus}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{prop}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{question}{Question$\!\!$}   
\renewcommand{\thequestion}{}
\newtheorem{conj}{Conjecture}

\theoremstyle{remark}
\newtheorem{rem}{Remark$\!\!$}  
\renewcommand{\therem}{}

\newtheorem{rems}{Remarks$\!\!$}        
\renewcommand{\therems}{}

\topmargin -0.3in
\headsep 0.3in
\oddsidemargin 0in
\evensidemargin 0in
\textwidth 6.5in
\textheight 9in

%%% \renewcommand{\baselinestretch}{3}

\begin{document}

\title{Linear recursive sequences}
%\subjclass{Primary 9999}
%\keywords{9999}
\author{Bjorn Poonen}
\address{Department of Mathematics, University of California, Berkeley, CA 
94720-3840, USA}
\email{poonen@math.berkeley.edu}
%\date{October 11, 1998}

%\begin{abstract}
%\end{abstract}

\maketitle

%****************************************************************************
\section{Sequences}
\label{sequences}

A {\em sequence} is an infinite list of numbers, like
\begin{equation}
\label{seq1}
        1, 2, 4, 8, 16, 32, \dots.
\end{equation}
The numbers in the sequence are called its {\em terms}.
The general form of a sequence is
        $$a_1, a_2, a_3, \dots$$
where $a_n$ is the $n$-th term of the sequence.
In the example~(\ref{seq1}) above, $a_1=1$, $a_2=2$, $a_3=4$, and so on.

The notations $\{a_n\}$ or $\{a_n\}_{n=1}^\infty$
are abbreviations for
        $$a_1, a_2, a_3, \dots.$$
Occasionally the indexing of the terms will start with something other
than~1.  For example, $\{a_n\}_{n=0}^\infty$ would mean
        $$a_0, a_1, a_2, \dots.$$
(In this case $a_n$ would be the $(n+1)$-st term.)

For some sequences, it is possible to give an {\em explicit formula}
for $a_n$: this means that $a_n$ is expressed as a function of $n$.
For instance, the sequence~(\ref{seq1}) above can be described by
the explicit formula $a_n = 2^{n-1}$.


%****************************************************************************
\section{Recursive definitions}
\label{recursive}

An alternative way to describe a sequence is to list a few terms
and to give a rule for computing the rest of the sequence.
Our example~(\ref{seq1}) above can be described by
the starting value $a_1=1$ and the rule $a_{n+1}=2a_n$
for integers $n \ge 1$.
Starting from $a_1=1$, the rule implies that
\begin{align*}
        a_2 &= 2a_1 = 2(1) = 2 \\
        a_3 &= 2a_2 = 2(2) = 4 \\
        a_4 &= 2a_3 = 2(4) = 8,
\end{align*}
and so on; each term in the sequence can be computed recursively
in terms of the terms previously computed.
A rule such as this giving the next term in terms of earlier terms
is also called a {\em recurrence relation} (or simply {\em recurrence}).

%****************************************************************************
\section{Linear recursive sequences}
\label{linearrecursive}

A sequence $\{a_n\}$
is said to satisfy the {\em linear recurrence}
with coefficients $c_k$, $c_{k-1}$, \dots, $c_0$
if
\begin{equation}
\label{linrec}
        c_k a_{n+k} + c_{k-1} a_{n+k-1} + \cdots + c_1 a_{n+1} + c_0 a_n = 0
\end{equation}
holds for all integers $n$ for which this makes sense.
(If the sequence starts with $a_1$, then this means for $n \ge 1$.)
The integer $k$ is called the {\em order} of the linear recurrence.

A {\em linear recursive sequence}
is a sequence of numbers $a_1,a_2,a_3,\dots$
satisfying some linear recurrence as above
with $c_k \not= 0$ and $c_0 \not=0$.
For example, the sequence~(\ref{seq1}) satisfies
        $$a_{n+1} - 2 a_n = 0$$
for all integers $n \ge 1$,
so it is a linear recursive sequence satisfying
a recurrence of order~1,
with $c_1=1$ and $c_0=-2$.

Requiring $c_k \not= 0$ guarantees that
the linear recurrence can be used to express $a_{n+k}$
as a linear combination of earlier terms:
        $$a_{n+k} = -\frac{c_{k-1}}{c_k} a_{n+k-1} - \cdots
                - \frac{c_1}{c_k} a_{n+1} - \frac{c_0}{c_k} a_n.$$
The requirement $c_0 \not=0$ lets one express $a_n$
as a linear combination of {\em later} terms:
        $$a_n = -\frac{c_k}{c_0} a_{n+k} -\frac{c_{k-1}}{c_0} a_{n+k-1}
                - \cdots - \frac{c_1}{c_0} a_{n+1}.$$
This lets one {\em define} $a_0$, $a_{-1}$, and so on,
to obtain a {\em doubly infinite sequence}
        $$\dots,a_{-2},a_{-1},a_0,a_1,a_2,\dots$$
that now satisfies the same linear recurrence for {\em all} integers $n$,
positive or negative.

%****************************************************************************
\section{Characteristic polynomials}
\label{charpoly}

The {\em characteristic polynomial} of a linear recurrence
        $$c_k a_{n+k} + c_{k-1} a_{n+k-1} + \cdots + c_1 a_{n+1} + c_0 a_n
        = 0$$
is defined to be the polynomial
        $$c_k x^k + c_{k-1} x^{k-1} + \cdots + c_1 x + c_0.$$
For example, the characteristic polynomial of
the recurrence $a_{n+1}-2a_n=0$ satisfied by the sequence~(\ref{seq1}) 
is $x-2$.

Here is another example: the famous {\em Fibonacci sequence}
        $$\{F_n\}_{n=0}^\infty = 0, 1, 1, 2, 3, 5, 8, 13, \dots$$
which can be described by the starting values $F_0=0$, $F_1=1$
and the recurrence relation
\begin{equation}
\label{fibrec}
        F_n=F_{n-1}+F_{n-2}     \qquad\text{for all $n \ge 2$.}
\end{equation}

To find the characteristic polynomial, we first need to
rewrite the recurrence relation in the form~(\ref{linrec}).
The relation~(\ref{fibrec}) is equivalent to
\begin{equation}
\label{fibrec2}
        F_{n+2}=F_{n+1}+F_n     \qquad\text{for all $n \ge 0$.}
\end{equation}
Rewriting it as
\begin{equation}
\label{fibrec3}
        F_{n+2}-F_{n+1}-F_n=0
\end{equation}
shows that $\{F_n\}$ is a linear recursive sequence satisfying
a recurrence of order~2,
with $c_2=1$, $c_1=-1$, and $c_0=-1$.
The characteristic polynomial is $x^2-x-1$.


%****************************************************************************
\section{Ideals and minimal characteristic polynomials}
\label{ideals}

The same sequence can satisfy many different linear recurrences.
For example, doubling~(\ref{fibrec3})
shows the Fibonacci sequence also satisfies
        $$2 F_{n+2} - 2 F_{n+1} - 2F_n = 0,$$
which is a linear recurrence with characteristic polynomial $2x^2-2x-2$.
It also satisfies
        $$F_{n+3} - F_{n+2} - F_{n+1} = 0,$$
and adding these two relations, we find that $\{F_n\}$ also satisfies
        $$F_{n+3} + F_{n+2} - 3 F_{n+1} - 2 F_n = 0$$
which has characteristic polynomial $x^3+x^2-3x-2=(x+2)(x^2-x-1)$.

Now consider an arbitrary sequence $\{a_n\}$.
Let $I$ be the set of characteristic polynomials
of {\em all} linear recurrences satisfied by $\{a_n\}$.
Then
\begin{enumerate}
        \item[(a)] If $f(x) \in I$ and $g(x) \in I$ then $f(x)+g(x) \in I$.
        \item[(b)] If $f(x) \in I$ and $h(x)$ is any polynomial,
                        then $h(x) f(x) \in I$.
\end{enumerate}
In general, a nonempty set $I$ of polynomials
satisfying~(a) and~(b)
is called an {\em ideal}.

\vspace{4 ex}
\noindent{\bf Fact from algebra:}
Let $I$ be an ideal of polynomials.
Then either $I=\{0\}$ or else there is a unique monic polynomial $f(x) \in I$
such that
        $$I = \text{the set of polynomial multiples of $f(x)$}
                = \{\, h(x)f(x) \mid h(x) \text{ is a polynomial} \,\}.$$
(A polynomial is {\em monic} if the coefficient of the highest power of $x$
is~1.)

\vspace{4 ex}

\noindent
This fact, applied to the ideal of characteristic polynomials
of a linear recursive sequence $\{a_n\}$
shows that there is always a {\em minimal characteristic polynomial} $f(x)$,
which is the monic polynomial of lowest degree in $I$.
It is the characteristic polynomial of the lowest order non-trivial
linear recurrence satisfied by $\{a_n\}$.
The characteristic polynomial of
any other linear recurrence satisfied by $\{a_n\}$
is a polynomial multiple of $f(x)$.

The {\em order} of a linear recursive sequence $\{a_n\}$
is defined to be the lowest order among all (nontrivial) linear recurrences
satisfied by $\{a_n\}$.
The order also equals the degree of the minimal characteristic polynomial.
For example, as we showed above, $\{F_n\}$ satisfies
        $$F_{n+3} + F_{n+2} - 3 F_{n+1} - 2 F_n = 0,$$
but we also know that
        $$F_{n+2}-F_{n+1}-F_n=0,$$
and it is easy to show that $\{F_n\}$ cannot satisfy a
linear recurrence of order less than~2,
so $\{F_n\}$ is a linear recursive sequence of order~2,
with minimal characteristic polynomial $x^2-x-1$.


%****************************************************************************
\section{The main theorem}
\label{maintheorem}

\begin{theorem}
\label{main}
Let $f(x)=c_k x^k + \cdots + c_0$
be a polynomial with $c_k \not= 0$ and $c_0 \not=0$.
Factor $f(x)$ over the complex numbers as
        $$f(x) = c_k (x-r_1)^{m_1} (x-r_2)^{m_2}
               \cdots (x-r_\ell)^{m_\ell},$$
where $r_1,r_2,\dots,r_\ell$ are distinct nonzero complex numbers,
and $m_1,m_2,\dots,m_\ell$ are positive integers.
Then a sequence $\{a_n\}$ satisfies the linear recurrence
with characteristic polynomial $f(x)$ if and only if
there exist polynomials $g_1(n)$, $g_2(n)$, \dots, $g_\ell(n)$
with $\deg g_i \le m_i-1$ for $i=1,2,\dots,\ell$ such that
        $$a_n = g_1(n) r_1^n + \cdots + g_\ell(n) r_\ell^n
                \qquad\text{for all $n$}.$$
\end{theorem}

Here is an important special case.

\begin{cor}
Suppose in addition that $f(x)$ has no repeated factors;
in other words suppose that $m_1=m_2=\cdots=m_\ell=1$.
Then $f(x)=c_k(x-r_1)(x-r_2)\cdots(x-r_\ell)$
where $r_1,r_2,\dots,r_\ell$ are distinct nonzero complex numbers
(the roots of $f$).
Then $\{a_n\}$ satisfies the linear recurrence
with characteristic polynomial $f(x)$ if and only if
there exist constants $B_1, B_2, \dots, B_\ell$ (not depending on $n$)
such that
        $$a_n = B_1 r_1^n + \cdots + B_\ell r_\ell^n
                \qquad\text{for all $n$}.$$
\end{cor}

%****************************************************************************
\section{Example: solving a linear recurrence}

Suppose we want to find an explicit formula for
the sequence $\{a_n\}$ satisfying $a_0=1$, $a_1=4$,
and
\begin{equation}
\label{averagerec}
        a_{n+2}= \frac{a_{n+1}+a_n}{2} \text{ for $n \ge 0$.}
\end{equation}
Since $\{a_n\}$ satisfies a linear recurrence with characteristic polynomial \\
$x^2-\frac12 x -\frac12 = (x-1)(x+\frac12)$,
we know that there exist constants $A$ and $B$
such that
\begin{equation}
\label{generalsolution}
        a_n = A (1)^n + B \left( -\frac12 \right)^n
\end{equation}
for all $n$.
The formula~(\ref{generalsolution}) is called the {\em general solution}
to the linear recurrence~(\ref{averagerec}).
To find the {\em particular solution} with the correct values of $A$ and $B$,
we use the known values of $a_0$ and $a_1$:
        $$1 = a_0 = A (1)^0 + B \left( -\frac12 \right)^0 = A+B$$
        $$4 = a_1 = A (1)^1 + B \left( -\frac12 \right)^1 = A - B/2.$$
Solving this system of equations yields $A=3$ and $B=-2$.
Thus the particular solution is
        $$a_n = 3 - 2 \left( -\frac12 \right)^n.$$
(As a check, one can try plugging in $n=0$ or $n=1$.)


%****************************************************************************
\section{Example: the formula for the Fibonacci sequence}

As we worked out earlier, $\{F_n\}$ satisfies
a linear recurrence with characteristic polynomial $x^2-x-1$.
By the quadratic formula, this factors as $(x-\alpha)(x-\beta)$
where $\alpha=(1+\sqrt{5})/2$ is the golden ratio,
and $\beta=(1-\sqrt{5})/2$.
The main theorem implies that there are constants $A$ and $B$
such that
        $$F_n = A \alpha^n + B \beta^n$$
for all $n$.
Using $F_0=0$ and $F_1=1$ we obtain
        $$0 = A + B, \qquad 1= A \alpha+B \beta.$$
Solving for $A$ and $B$ yields $A=1/(\alpha-\beta)$ and $B=-1/(\alpha-\beta)$,
so
        $$F_n = \frac{\alpha^n-\beta^n}{\alpha-\beta}
        = \frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2} \right)^n
                - \left(\frac{1-\sqrt{5}}{2} \right)^n \right]$$
for all $n$.

%****************************************************************************
\section{Example: finding a linear recurrence from an explicit formula}

Let $a_n=(n+2^n)F_n$, where $\{F_n\}$ is the Fibonacci sequence.
Then by the explicit formula for $F_n$,
\begin{align*}
        a_n &= (n+2^n) \left( \frac{\alpha^n-\beta^n}{\alpha-\beta} \right) \\
        &= \left[ \left( \frac{1}{\alpha-\beta} \right) n \right] \alpha^n
         + \left[ \left( \frac{-1}{\alpha-\beta} \right) n \right] \beta^n
        + \left( \frac{1}{\alpha-\beta} \right) (2\alpha)^n
        + \left( \frac{-1}{\alpha-\beta} \right) (2\beta)^n.
\end{align*}
By Theorem~\ref{main}, $\{a_n\}$ satisfies a linear recurrence with
characteristic polynomial
\begin{align*}
        (x-\alpha)^2(x-\beta)^2(x-2\alpha)(x-2\beta)
        &= (x^2-x-1)^2 \left[ x^2-2(\alpha+\beta)+4\alpha\beta \right]  \\
        &= (x^2-x-1)^2(x^2-2x-4)        \\
        &= x^6-4x^5-x^4+12x^3+x^2-10x+4,
\end{align*}
where we have used the identity $x^2-(\alpha+\beta)x+\alpha\beta=x^2-x-1$
to compute $\alpha+\beta$ and $\alpha\beta$.
In other words,
        $$a_{n+6} - 4 a_{n+5} - a_{n+4} + 12 a_{n+3}
                + a_{n+2} - 10 a_{n+1} + 4 a_n = 0$$
for all $n$.
In fact, we have found the minimal characteristic polynomial,
since if the actual minimal characteristic polynomial
were a proper divisor of $(x^2-x-1)^2(x^2-2x-4)$,
then according to Theorem~\ref{main},
the explicit formula for $a_n$ would have had a different, simpler form.


%****************************************************************************
\section{Inhomogeneous recurrence relations}

Suppose we wanted an explicit formula for a sequence $\{a_n\}$
satisfying $a_0=0$, and
\begin{equation}
\label{inhomeqn}
        a_{n+1}-2a_n = F_n \qquad \text{for $n \ge 0$},
\end{equation}
where $\{F_n\}$ is the Fibonacci sequence as usual.
This is not a linear recurrence in the sense we have been talking about
(because of the $F_n$ on the right hand side instead of~0),
so our usual method does not work.
A recurrence of this type, linear except for a function of $n$
on the right hand side,
is called an {\em inhomogeneous recurrence}.

We can solve inhomogeneous recurrences explicitly when the right hand side
is itself a linear recursive sequence.
In our example, $\{a_n\}$ also satisfies
\begin{equation}
\label{inhomeqn2}
        a_{n+2}-2a_{n+1} = F_{n+1}
\end{equation}
and
\begin{equation}
\label{inhomeqn3}
        a_{n+3}-2a_{n+2} = F_{n+2}.
\end{equation}
Subtracting~(\ref{inhomeqn}) and~(\ref{inhomeqn2}) from~(\ref{inhomeqn3})
yields
        $$a_{n+3}-3a_{n+2}+a_{n+1}+2a_n = F_{n+2}-F_{n+1}-F_n = 0.$$
Thus $\{a_n\}$ is a linear recursive sequence after all!
The characteristic polynomial of this new linear recurrence is
$x^3-3x^2+x+2=(x-2)(x^2-x-1)$,
so by Theorem~\ref{main}, there exist constants $A,B,C$ such that
        $$a_n=A \cdot 2^n + B \alpha^n + C \beta^n$$
for all $n$.
Now we can use $a_0=0$, and the values $a_1=0$ and $a_2=1$
obtained from~(\ref{inhomeqn}) to determine $A,B,C$.
After some work, one finds $A=1$, $B=-\alpha^2/(\alpha-\beta)$,
and $C=\beta^2/(\alpha-\beta)$, so $a_n = 2^n - F_{n+2}.$

\medskip

If $\{x_n\}$ is any other sequence satisfying
\begin{equation}
\label{generalinhom}
        x_{n+1}-2x_n = F_n
\end{equation}
but not necessarily $x_0=0$,
then subtracting~(\ref{inhomeqn}) from~(\ref{generalinhom})
shows that the sequence $\{y_n\}$ defined by $y_n=x_n-a_n$
satisfies $y_{n+1}-2y_n=0$
for all $n$, so $y_n=D \cdot 2^n$ for some number $D$.
Hence the {\em general solution} of~(\ref{generalinhom})
has the form
        $$x_n = 2^n - F_{n+2} + D \cdot 2^n,$$
or more simply,
        $$x_n = E \cdot 2^n - F_{n+2},$$
where $E$ is some constant.

In general, this sort of argument proves the following.

\begin{theorem}
Let $\{b_n\}$ be a linear recursive sequence satisfying a recurrence
with characteristic polynomial $f(x)$.
Let $g(x)=c_k x^k + c_{k-1} x^{k-1} + \cdots + c_1 x + c_0$
be a polynomial.
Then every solution $\{x_n\}$ to the inhomogeneous recurrence
\begin{equation}
\label{biginhom}
        c_k x_{n+k} + c_{k-1} x_{n+k-1} + \cdots + c_1 x_{n+1} + c_0 x_n
        = b_n
\end{equation}
also satisfies a linear recurrence with characteristic polynomial $f(x)g(x)$.

Moreover, if $\{x_n\}=\{a_n\}$ is one particular solution to~(\ref{biginhom}),
then all solutions have the form $x_n = a_n + y_n$,
where $\{y_n\}$ ranges over the solutions of the linear recurrence
        $$c_k y_{n+k} + c_{k-1} y_{n+k-1} + \cdots + c_1 y_{n+1} + c_0 y_n
        = 0.$$
\end{theorem}

%****************************************************************************
\section{The Mahler-Lech theorem}

Here is a deep theorem about linear recursive sequences:

\begin{theorem}[Mahler-Lech theorem]
Let $\{a_n\}$ be a linear recursive sequence
of complex numbers, and let $c$ be a complex number.
Then there exists a finite (possibly empty) list of arithmetic progressions
$T_1$, $T_2$, \dots $T_m$
and a finite (possibly empty) set $S$ of integers
such that
        $$\{\, n \mid a_n=c \,\} = S \cup T_1 \cup T_2 \cup \cdots \cup T_m.$$
\end{theorem}

Warning: don't try to prove this at home!
This is {\em very} hard to prove.
The proof uses ``$p$-adic numbers.''
% See p.~88 of Cassels, {\em Local fields}, Cambridge Univ.\ Press, 1986.


%****************************************************************************
\section{Problems}
\label{problems}

There are a lot of problems here.
Just do the ones that interest you.

\begin{enumerate}

\item
If the Fibonacci sequence is extended to a doubly infinite sequence
satisfying the same linear recurrence,
then what will $F_{-4}$ be?
(Is it easier to do this using the recurrence,
or using the explicit formula?)

\item
Find the smallest degree polynomial that could be the minimal characteristic
polynomial of a sequence that begins

        $$2, 5, 18, 67, 250, 933, \dots.$$
Assuming that the sequence {\em is} a linear recursive sequence
with this characteristic polynomial,
find an explicit formula for the $n$-th term.

\item
Suppose that $a_n=n^2+3n+7$ for $n \ge 1$.
Prove that $\{a_n\}$ is a linear recursive sequence,
and find its minimal characteristic polynomial.

\item
Suppose $a_1=a_2=a_3=1$, $a_4=3$, and $a_{n+4}=3 a_{n+2} - 2 a_n$
for $n \ge 1$.
Prove that $a_n=1$ if and only if $n$ is odd or $n=2$.
(This is an instance of the Mahler-Lech theorem:
for this sequence, one would take $S=\{2\}$ and
$T_1=\{1,3,5,7,\dots\}$.)

\item
Suppose $a_0=2$, $a_1=5$, and $a_{n+2}=(a_{n+1})^2 (a_n)^3$ for $n \ge 0$.
(This is a recurrence relation, but not a linear recurrence relation.)
Find an explicit formula for $a_n$.

\item
Suppose $\{a_n\}$ is a sequence such that $a_{n+2}=a_{n+1}-a_n$
for all $n \ge 1$.
Given that $a_{38}=7$ and $a_{55}=3$, find $a_1$.
(Hint: it is possible to solve this problem with very little calculation.)

\item
Let $\theta$ be a fixed real number,
and let $a_n=\cos(n \theta)$ for integers $n \ge 1$.
Prove that $\{a_n\}$ is a linear recursive sequence,
and find the minimal characteristic polynomial.
(Hint: if you know the definition of $\cos x$ in terms of complex
exponentials, use that.
Otherwise, use the sum-to-product rule for the sum of cosines
$\cos(n \theta)+\cos((n+2) \theta)$.
For most but not all $\theta$,
the degree of the minimal characteristic polynomial will be~2.)

\item Give an example of a sequence that is {\em not}
a linear recursive sequence, and prove that it is not one.

\item Given a finite set $S$ of positive integers, show that there
exists a linear recursive sequence
        $$a_1, a_2, a_3, \dots$$

such that $\{\, n \mid a_n=0 \,\} = S$.

\item
A student tosses a fair coin and scores one point for each head
that turns up, and two points for each tail.
Prove that the probability of the student scoring $n$ points
at some time in a sequence of $n$ tosses is
$\frac{1}{3} \left( 2 + (-\frac{1}{2})^n \right)$.

\item
Let $F_n$ denote the $n$-th Fibonacci number.
Let $a_n=(F_n)^2$.
Prove that $a_1,a_2,a_3,\dots$ is a linear recursive sequence,
and find its minimal characteristic polynomial.

\item
Prove the ``fact from algebra'' mentioned above in Section~\ref{ideals}.
(Hint: if $I \not= \{0\}$,
pick a nonzero polynomial in $I$ of smallest degree,
and multiply it by a constant to get a monic polynomial $f(x)$.
Use long division of polynomials to show that anything else in $I$
is a polynomial multiple of $f(x)$.)

\item
Suppose that $a_1,a_2,\dots$ is a linear recursive sequence.
For $n \ge 1$, let $s_n=a_1+a_2+\cdots+a_n$.
Prove that $\{s_n\}$ is a linear recursive sequence.

\item
Suppose $\{a_n\}$ and $\{b_n\}$ are linear recursive sequences.
Let $c_n = a_n + b_n$ and $d_n=a_n b_n$ for $n \ge 1$.

(a) Prove that $\{c_n\}$ and $\{d_n\}$ also are linear recursive sequences.

(b) Suppose that the minimal characteristic polynomials for
$\{a_n\}$ and $\{b_n\}$ are $x^2-x-2$ and $x^2-5x+6$, respectively.
What are the possibilities
for the minimal characteristic polynomials of $\{c_n\}$ and $\{d_n\}$?

\item
Suppose that $\{a_n\}$ and $\{b_n\}$ are linear recursive sequences.
Prove that
        $$a_1,b_1,a_2,b_2,a_3,b_3,\dots$$
also is a linear recursive sequence.

\item
Use the Mahler-Lech theorem to prove the following generalization.

Let $\{a_n\}$ be a linear recursive sequence
of complex numbers, and let $p(x)$ be a polynomial.
Then there exists a finite (possibly empty) list of arithmetic progressions
$T_1$, $T_2$, \dots $T_m$
and a finite (possibly empty) set $S$ of integers
such that
        $$\{\, n \mid a_n=p(n)\,\}
        = S \cup T_1 \cup T_2 \cup \cdots \cup T_m.$$
(Hint: let $b_n=a_n-p(n)$.)

\item
(1973 USAMO, no.~2)
Let $\{X_n\}$ and $\{Y_n\}$ denote two sequences of integers defined
as follows:
        $$X_0=1, X_1=1, X_{n+1} = X_n + 2 X_{n-1} \quad (n=1,2,3,\dots),$$
        $$Y_0=1, Y_1=7, Y_{n+1} = 2 Y_n + 3 Y_{n-1} \quad (n=1,2,3,\dots).$$
Thus, the first few terms of the sequences are:
        $$X: 1,1,3,5,11,21,\dots,$$
        $$Y: 1,7,17,55,161,487,\dots.$$
Prove that, except for the ``1,'' there is no term which occurs
in both sequences.

\item
(1963 IMO, no.~4)
Find all solutions $x_1,x_2,x_3,x_4,x_5$ to the system
\begin{align*}
        x_5 + x_2 &= y x_1      \\
        x_1 + x_3 &= y x_2      \\
        x_2 + x_4 &= y x_3      \\
        x_3 + x_5 &= y x_4      \\
        x_4 + x_1 &= y x_5,
\end{align*}
where $y$ is a parameter.
(Hint: define $x_6=x_1$, $x_7=x_2$, etc., and find two different
linear recurrences satisfied by $\{x_n\}$.)

\item
(1967 IMO, no.~6)
In a sports contest,
there were $m$ medals awarded on $n$ successive days ($n>1$).
On the first day,
one medal and $1/7$ of the remaining $m-1$ medals were awarded.
On the second day,
two medals and $1/7$ of the now remaining medals were awarded; and so on.
On the $n$-th and last day, the remaining $n$ medals were awarded.
How many days did the contest last,
and how many medals were awarded altogether?

item
(1974 IMO, no.~3)
Prove that the number $\sum_{k=0}^n \binom{2n+1}{k+1} 2^{3k}$
is not divisible by~5 for any integer $n \ge 0$.

\item
(1980 USAMO, no.~3)
Let $F_r = x^r \sin(rA) + y^r \sin(rB) + z^r \sin(rC)$,
where $x,y,z,A,B,C$ are real and $A+B+C$ is an integral multiple of $\pi$.
Prove that if $F_1=F_2=0$, then $F_r=0$ for all positive integral $r$.

\end{enumerate}

\vfill
{\tiny \copyright Berkeley Math Circle}

%****************************************************************************

\end{document}