Problems

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

- If the Fibonacci sequence is extended to a doubly infinite sequence
satisfying the same linear recurrence,
then what will be?
(Is it easier to do this using the recurrence,
or using the explicit formula?)
- Find the smallest degree polynomial that could be the minimal characteristic
polynomial of a sequence that begins
*is*a linear recursive sequence with this characteristic polynomial, find an explicit formula for the -th term. - Suppose that
for .
Prove that is a linear recursive sequence,
and find its minimal characteristic polynomial.
- Suppose
, , and
for .
Prove that if and only if is odd or .
(This is an instance of the Mahler-Lech theorem:
for this sequence, one would take and
.)
- Suppose , , and
for .
(This is a recurrence relation, but not a linear recurrence relation.)
Find an explicit formula for .
- Suppose is a sequence such that
for all .
Given that and , find .
(Hint: it is possible to solve this problem with very little calculation.)
- Let be a fixed real number,
and let
for integers .
Prove that is a linear recursive sequence,
and find the minimal characteristic polynomial.
(Hint: if you know the definition of in terms of complex
exponentials, use that.
Otherwise, use the sum-to-product rule for the sum of cosines
.
For most but not all ,
the degree of the minimal characteristic polynomial will be 2.)
- Give an example of a sequence that is
*not*a linear recursive sequence, and prove that it is not one. - Given a finite set of positive integers, show that there
exists a linear recursive sequence
such that .

- 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 points
at some time in a sequence of tosses is
.
- Let denote the -th Fibonacci number.
Let
.
Prove that
is a linear recursive sequence,
and find its minimal characteristic polynomial.
- Prove the ``fact from algebra'' mentioned above in Section 5.
(Hint: if
,
pick a nonzero polynomial in of smallest degree,
and multiply it by a constant to get a monic polynomial .
Use long division of polynomials to show that anything else in
is a polynomial multiple of .)
- Suppose that
is a linear recursive sequence.
For , let
.
Prove that is a linear recursive sequence.
- Suppose and are linear recursive sequences.
Let
and
for .
(a) Prove that and also are linear recursive sequences.

(b) Suppose that the minimal characteristic polynomials for and are and , respectively. What are the possibilities for the minimal characteristic polynomials of and ?

- Suppose that and are linear recursive sequences.
Prove that
- Use the Mahler-Lech theorem to prove the following generalization.
Let be a linear recursive sequence of complex numbers, and let be a polynomial. Then there exists a finite (possibly empty) list of arithmetic progressions , , ... and a finite (possibly empty) set of integers such that

- (1973 USAMO, no. 2)
Let and denote two sequences of integers defined
as follows:
- (1963 IMO, no. 4)
Find all solutions
to the system

where is a parameter. (Hint: define , , etc., and find two different linear recurrences satisfied by .) - (1967 IMO, no. 6)
In a sports contest,
there were medals awarded on successive days ().
On the first day,
one medal and of the remaining medals were awarded.
On the second day,
two medals and of the now remaining medals were awarded; and so on.
On the -th and last day, the remaining 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 is not divisible by 5 for any integer .

- (1980 USAMO, no. 3)
Let
,
where
are real and is an integral multiple of .
Prove that if , then for all positive integral .

©Berkeley Math Circle