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 $F_{-4}$ 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
   $$2, 5, 18, 67, 250, 933, \dots.$$
   Assuming that the sequence is a linear recursive sequence with this characteristic polynomial, find an explicit formula for the $n$-th term.

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

4. 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\}$.)

5. 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$.

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

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

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

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 $n$ points at some time in a sequence of $n$ tosses is $\frac{1}{3} \left( 2 + (-\frac{1}{2})^n \right)$.

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

12. Prove the ``fact from algebra'' mentioned above in Section 5. (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)$.)

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

14. 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\}$?

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

16. 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$, ...$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)$.)

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

18. (1963 IMO, no. 4) Find all solutions $x_1,x_2,x_3,x_4,x_5$ to the system

    $$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,$$

    
    
    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\}$.)

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

20. (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$.

©Berkeley Math Circle