8. let $m$ be a natural number greater than 1 . the sequence $x_{0}, x_{1}, x_{2}, \ldots$ is defined by

$$
x_{i}= \begin{cases}2^{i}, & \text { for } \quad 0 \leq i \leq m-1 \\ \sum_{j=1}^{m} x_{i-j} & \text { for } \quad i \geq m\end{cases}
$$

Find the largest $k$ such that there are $k$ consecutive sequential elements that are all divisible by $m$.
## Solution

Let $r_{i}$ be the remainder of $x_{i}$ when divided by $m$. Instead of the sequence $\left(x_{i}\right)$, we consider the sequence $\left(r_{i}\right)$. The recursion formula can be used to calculate the next, but also the previous one, from $m$ consecutive sequence members. Such $m$ consecutive links therefore determine the entire sequence. Because of $0 \leq r_{i} \leq m-1$ there are at most $m^{m}$ different $m$-tuples $\left(r_{i}, r_{i+1}, \ldots, r_{i+m-1}\right)$ of consecutive sequence members. According to the drawer principle, one of these $m$ tuples occurs several times in the sequence. This means that the sequence is periodic without a previous period (the elements can be calculated backwards).

Assume that $m$ consecutive $x_{i}$ are divisible by $m$. Then the sequence contains

( $\left.r_{i}\right) m$ consecutive zeros and from the recursion formula it follows that all sequence members are equal to zero, in contradiction to $x_{0}=r_{0}=1$.

On the other hand, the sequence $x_{i}$ can be continued backwards beyond $x_{0}$. The formula $x_{i}=x_{i+m}-\sum_{j=1}^{m-1} x_{i+j}$ now easily yields $x_{-1}=1$ and further $x_{-2}=x_{-3}=\ldots=x_{-m}=$ 0 . Due to the periodicity of $\left(r_{i}\right)$, there are therefore $m-1$ consecutive members in $\left(x_{i}\right)_{i \geq 0}$ that are divisible by $m$.