next up previous
Next: About this document ... Up: Linear recursive sequences Previous: The Mahler-Lech theorem


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

    $\displaystyle 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

    $\displaystyle 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

    $\displaystyle 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

    $\displaystyle \{  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:

    $\displaystyle X_0=1, X_1=1, X_{n+1} = X_n + 2 X_{n-1} \quad (n=1,2,3,\dots),$

    $\displaystyle 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:

    $\displaystyle X: 1,1,3,5,11,21,\dots,$

    $\displaystyle 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

    $\displaystyle x_5 + x_2$ $\displaystyle = y x_1$    
    $\displaystyle x_1 + x_3$ $\displaystyle = y x_2$    
    $\displaystyle x_2 + x_4$ $\displaystyle = y x_3$    
    $\displaystyle x_3 + x_5$ $\displaystyle = y x_4$    
    $\displaystyle x_4 + x_1$ $\displaystyle = 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

next up previous
Next: About this document ... Up: Linear recursive sequences Previous: The Mahler-Lech theorem
Zvezdelina Stankova-Frenkel 2000-09-20