# Problems

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

1. 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?)

2. Find the smallest degree polynomial that could be the minimal characteristic polynomial of a sequence that begins

Assuming that the sequence is a linear recursive sequence with this characteristic polynomial, find an explicit formula for the -th term.

3. Suppose that for . Prove that is a linear recursive sequence, and find its minimal characteristic polynomial.

4. 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 .)

5. Suppose , , and for . (This is a recurrence relation, but not a linear recurrence relation.) Find an explicit formula for .

6. Suppose is a sequence such that for all . Given that and , find . (Hint: it is possible to solve this problem with very little calculation.)

7. 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.)

8. Give an example of a sequence that is not a linear recursive sequence, and prove that it is not one.

9. Given a finite set of positive integers, show that there exists a linear recursive sequence

such that .

10. 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 .

11. Let denote the -th Fibonacci number. Let . Prove that is a linear recursive sequence, and find its minimal characteristic polynomial.

12. 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 .)

13. Suppose that is a linear recursive sequence. For , let . Prove that is a linear recursive sequence.

14. 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 ?

15. Suppose that and are linear recursive sequences. Prove that

also is a linear recursive sequence.

16. 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

(Hint: let .)

17. (1973 USAMO, no. 2) Let and denote two sequences of integers defined as follows:

Thus, the first few terms of the sequences are:

Prove that, except for the 1,'' there is no term which occurs in both sequences.

18. (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 .)

19. (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 .

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