Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

I know it has been discussed beofre, but what's the question?

http://www.mathlinks.ro/Forum/viewtopic.php?t=5643 Darij

When I click that it tells me something like "we're moving to a better forum.." or "URL not found..". Does this happen to anyone else?

Not to me... Here is the address: Mathlinks Forum Index -> Problem Solving -> MathLinks Olympiad Forum -> Advanced Section -> Number Theory -> Number Theory Proposed & Own Problems -> Sequence Darij

...question is: Find the greatest $k$ for which the sequence contains $k$ consecutive terms divisible by $m$ .

I claim that the answer is $ k = m - 1 $. Lemma 1: $ k \geq m $ is impossible Proof: Consider the sequence modulo $ m $. Assume the contrary, so that there is a string of $ m $ consecutive $ 0 $'s somewhere in the sequence. Using the recursive formula, we find that the element of the sequence immediately before the string of $ 0 $'s is also a $ 0 $. Continuing in this fashion, we have that every element of this sequence is eqivalent to $ 0 \pmod m $, contradiction. Lemma 2: $ k = m - 1 $ is obtainable. Proof: Again consider the sequence modulo $ m $. Extend the sequence so that now the sequence is $ \dots x_{-3}, x_{-2}, x_{-1}, x_0, x_1, x_2, \dots $ so that the recursive formula holds for all $ i \in \mathbb{Z} $. Since $ 2^{m - 1} - \sum_{n = 0}^{m - 2}2^n = 1 $ we have that $ x_{-1} = 1 $. It is then easy to see that $ x_{-2} = x_{-3} = \dots = x_{-m} = 0 $. Since the sequence is infinite and since there are only $ m ^ m $ sequences of length $ m $ whose elements are in $ \mathbb{Z}_m $, we have because the sequence is defined recursively that the sequence taken modulo $ m $ is totally periodic (by the Pidgeonhole Principle). Therefore we can find a string of $ m - 1 $ $ 0 $'s in the sequence where the subscripts of the $ x $'s are all positive, as desired. Therefore the claim is proven.

Is it true? Xm+i = 2^i * (2^m-1) that is easy by induction and for m=2^a, a>=1, and i>a we get that Xm+i is divisible by m conclusion, we have infiniely k

We claim that the answer is $k=\boxed{m-1}$. First, we will prove that there cannot be $m$ consecutive multiples of $m$. Suppose there was, and the earliest copy of $m$ consecutive elements divisible by $m$ was from $x_{i+1}$ to $x_{i+m}$, with $i$ being a nonnegative integer. Then notice that $x_i=x_{i+m}-x_{i+m-1}-\ldots-x_{i+1}$, which must be a multiple of $m$, so $x_i$ to $x_{i+m-1}$ is a set of $m$ consecutive elements divisible by $m$, a contradiction as we said $x_{i+1}$ to $x_{i+m}$ was the first such set. Now we prove that for all $m$, there exists $m-1$ consecutive elements divisible by $m$. Extend the definition of $x_n$ to negative numbers using the recursion $x_i=x_{i+m}-x_{i+m-1}-\ldots-x_{i+1}$, which is already true for all nonnegative integers $i$, by extending this definition to all negative integers $i$ as well. Using this, we get $x_{-1}=1$ and $x_{-2}=x_{-3}=\ldots=x_{-m}=0$. Now let $y_i$ be the remainder of $x_i$ when divided by $m$, and consider the ordered $m$-tuple $(y_{i+1}, y_{i+2}, \ldots, y_{i+m})$ for all nonnegative integers $i$. Because there are only $m^m$ possible ordered $m$-tuples, there are infinitely many duplicates by the Pigeonhole principle. Suppose that two nonnegative integers $i$ and $j$ with $j-i\ge m$ are such duplicates, thus $y_{i+k}=y_{j+k}$ for all $1\le k\le m$. Then, using the recursion both forwards and backwards, we get $y_{i+k}=y_{j+k}$ for all integers $k$. Using $k=-i-p$ for $2\le p\le k$, we get $y_{-p}=y_{j-i-p}$. However, because $y_{-p}=0$, we get that $y_{j-i-p}=0$ for all $2\le p\le m$. Since $j-i>m, j-i-p$ must be positive for all $2\le p\le m$, so $y_n$ is $0$ for $m-1$ consecutive positive integer elements, and these elements correspond with $m-1$ consecutive elements that are multiples of $m$, and we are done.

We claim that $k=m-1.$ If there are at least $m$ consecutive terms of the sequence divisible by $m$, say, $x_{i+1},x_{i+2},...,x_{i+m}$ then \[x_{i+m}=x_{i+m-1}+...+x_{i+1}+x_i\]implies that $m$ divides $x_i$ as well. Continuing this process, we get that $m$ must divide $x_0=1$ which is a contradiction. Now to prove that $m-1$ works, observe that $x_{i+m},x_{i+m-1},...,x_{i+1}$ only depend on $x_i, x_{i-1},...,x_{i-m+1},$ i.e. the previous $m$ terms, and thus, by looking at blocks of $m$ elements, since there are finitely many possibilities for them (the terms are reduced modulo $m$) we can deduce that eventually we will get $(2^0,2^1,...,2^{m-1})_m$ again so the previous $m$ terms will be $(1,0,0...,0)_m$ so there are $m-1$ terms divisible by $m.$

Ans is $\boxed{m-1}$. Consider sequence $\pmod m$. First we will show that $k=m$ is impossible (also proves it for $k>m$). Suppose there were $m$ consecutive zeros. Let $i$ be the last of these $m$ values so that $x_i=0$. Then $x_{i-m}$, which is the term before these zeros is also $0$. Repeating this process gives every element is $0\pmod m$, a contradiction. Now we will show that $k=m-1$ always holds. Extend the sequence so that the same formula holds for all $i\in \mathbb{Z}$ and indices can also be negative. So \[2^{m-1}=x_{m-1}=2^{m-1}-1+x_{-1}\implies x_{-1}=1\] Thus, $x_{-2}=x_{-3}=\ldots=x_{-m}=0$. Consider in $\pmod m$, the ordered $m$-tuples $(x_i, x_{i+1}, \ldots,x_{i+m})$. Since there are only $m^m$ distinct such tuples, there must be infinitely many duplicates. Now if we have a tuple $(x_i, x_{i+1}, \ldots, x_{i+m})$, we can find $x_{i-1}$ and go all the way back to the tuple $(x_{-m},\ldots, x_{-1})\equiv (0,0,0,\ldots,0,0,1)$. Now with the duplicate, we can go back the same amount and find another $m$-tuple that is $(0,0,0\ldots,0,0,1)$, but this time the indices are positive.

Consecutive terms in fibonacci sequences starting with powers of two. Define a sequence $y_0,y_1,y_2,\dots$ that is equivalent to the sequence $x_0,x_1,x_2,\dots$ modulo $m.$ Note that by pigeonhole principle there must exist a term $y_k$ with $k>0$ such that \[\left(y_0,y_1,y_2,y_3,\dots,y_{m-1}\right)=\left(y_k,y_{k+1},\dots,y_{k+m-1}\right)\]Now, we see that $\left(y_k,y_{k+1},\dots,y_{k+m-1}\right)=\left(1,2,4,\dots,2^{m-1}\right)$ so $y_{k-1}=1,$ $y_{k-2}=0$ and $y_{k-i}=0$ for $i=2,\dots,m$ since $0+0+0+\dots+1+1+2+\dots+2^i=2^{i+1}.$ This makes a sequence of $m-1$ consecutive terms divisible by $m$ and we cannot get $m$ consecutive terms divisible by $m$ because then the cycle in $y_k$ would just always be $0,$ which would necessarily imply that $y_0=0$ which is clearly false as $y_0=1.$

The answer is $m-1$. Claim: It is impossible for $m$ consecutive terms in this sequence to be all divisible by $m$. Proof. Assume not, and say that the first time $m$ consecutive terms in this sequence are all divisible by $m$ are indices $x_{i-m}, x_{i-m+1}, \ldots, x_{i-1}$. It is clear that $i-m \geq 1$, and so $x_{i-m-1} = x_{i-1} - \sum\limits_{j = 1}^{m} x_{i-1-j}$ is also divisible by $m$. However, this means that $x_{i-m-1}, x_{i-m}, \ldots, x_{i-2}$ are all divisible by $m$, contradiction. $\blacksquare$ Now, we show the significantly harder step: that there exists some $m-1$ consecutive numbers in the sequence all divisible by $m$. Claim: There exists some $l$ such that $x_{l+i} \equiv x_{i} \pmod{m}$ (i.e., the sequence is periodic $\pmod{m}$.) Proof. We first show that the sequence is eventually periodic. There only exist finitely many possible strings of integers from $1$ to $m$ of length $m$, so there exist some distinct positive integers $a$ and $b$ such that \[ x_{a-i} \equiv x_{b-i} \pmod{m} [i \in \mathbb{Z}; \; 1 \leq i \leq m] \]However, by the recursion, this also implies $x_a \equiv x_b \pmod{m}$, $x_{a+1} \equiv x_{b+1} \pmod{m}$, etc. However, wlogging $a < b$, we can also take this recursion back to show that $x_0 \equiv x_{b-a} \pmod{p}$, and in general that $x_k \equiv x_{b-a+k} \pmod{p}$, which proves the claim by setting $l = b-a$. $\blacksquare$ Claim: [Magic] If $l$ is the length of the period, then $x_{kl-m}, x_{kl-m+1}, \ldots, x_{kl-2}$ are all divisble by $m$ for any positive integer $k$. (This claim clearly finishes). Proof. Assume $kl \geq m$. It is clear to see that $x_{kl} \equiv 1 \pmod{m}, x_{kl+1} \equiv 2 \pmod{m}, \ldots, x_{kl+m-1} \equiv 2^{m-1} \pmod{m}$ Working backwards gives us $x_{kl - 1} \equiv 2^{m-1} - \sum\limits_{i=0}^{m-2} 2^i \equiv 1 \pmod{m}$, $x_{kl-2} \equiv 2^{m-2} - \sum\limits_{i=0}^{m-3} - 1 \equiv 0 \pmod{m}$, and so on. In general, for integer $2 \leq j \leq m$, \[ x_{kl - j} \equiv 2^{m-j} - \sum\limits_{i=0}^{m-j-1} - 1 \equiv 0 \pmod{m} \]using the given recursion. $\blacksquare$

We claim the answer is $m-1$. If $k \ge m$, consider the first block of $m$ terms, $x_{i+1},x_{i+2},\dots x_{i+m}$ that are all divisible by $m$. This block obviously can't contain $x_1$ so $i \ge 1$. We thus have that by definition $x_i$ is divisible by $m$ contradicting the fact that it's the first block of $m$ terms. We now prove that $k=m-1$ is achievable. Extend $\{x_i\}$ to the negatives so that the recursive definition still holds. We get that $x_{-1}=1$ and $x_{-i}=0$ for all $2 \le i \le n$. If we prove that $\{x_i\}$ is periodic $\pmod{m}$ we will be done. Let $y_i := x_i \pmod{m}$. Consider the $m^m$ $m$-tuples where all the numbers are nonnegative and less than $m$. By PhP, we have that there is a $m$-tuple that appears more than once. However we can note that the sequence $y_i$ is fully determined by this $m$-tuple, so the sequence will be the same from these $m$-tuples just shifted, which implies the sequence is periodic and we are done.

The answer is $m-1$. Suppose for the sake of contradiction that $a$ is the minimum possible such that $x_a$ through $x_{a+m-1}$ are all multiples of $m$. Since $x_0$ is not a multiple of $m$, we have that $a\geq1$. Therefore, by the recursive rule, $x_{a-1}$ is also a multiple of $m$, contradicting minimality. Extend the sequence back $m-1$ terms, and they are all zeroes. There are only finitely many sequences of $m$ residues modulo $m$, so this sequence repeats and therefore contains $m-1$ consecutive zeroes.

ISL Marabot Solve Claim : $k < m$ Proof : FTSOC, $k\geq m$. Now we consider the sequence mod $m$. So, the sequence contains at least $m$ consecutive $0$. In any such $m$ tuple with all $0$, let $x_y$ be the first number which is $0$ mod $m$. So, $x_{y-1}\neq 0$ and $x_{y+1},\dots x_{y+m-1}=0$ mod $m$. But now, $x_{y+m-1}=x_{y+m-2}+\dots+ x_y+ x_{y-1}$ mod $m$, which gives $x_{y-1}=0$ mod $m$. Contradiction. Claim : $k=n-1$ Proof : If we generalize the sequence to its negative terms, then the sequence becomes $x_i = \begin{cases}2^i&\text{if }0\leq i \leq m - 1;\\\sum_{j=1}^mx_{i-j}\end{cases}$. By using $x_{m-1}=2^{m-1}$, we get $x_{-1}= x_{m-1}-(x_{m-2}+\dots x_0)=2^{m-1}-(2^{m-1}-1)=1$ and similarly using $x_{-1}=1$ and $x_{m-2}=2^{m-2}$, we get $x_{-2}=0$. So, by induction, $x_{-i}=0$ for $2\leq i \leq m$. Again, we view the sequence mod $m$. Since it is an infinite recursive sequence, so by Pigeonhole principle, among any $m^m+1$ numbers of $m$ tuples, two are similar mod $m$. We can easily go backward and forward from two similar $m$ tuple to other two similar $m$ tuples (because the recursive sequence is formed by any $m$ tuples). Since we have a $m$ tuple with $m-1$'s consecutive $0$ and $1$'s $1$, we can go forward to another such a tuple mod $m$. Thus, $k=m-1$

The answer is $k = m - 1.$ Take the entire sequence mod $m$ to get the sequence $y_n.$ We will first note the following: Claim: There exists an integer $M$ such that for all $n \ge M,$ we have $y_{n} = y_{n + z},$ where $z$ is some positive integer. Proof: There are only a finite number of pairs $(y_n, y_{n+1}, \dots, y_{n+m-1}),$ so by Pigeonhole, at least two of these pairs are the same. This corresponds to the sequence being periodic at some point. We then know that $y_M = y_{M+z}, y_{M+1} = y_{M+z+1},$ and so on, up until $y_{M+m} = y_{M+m+z}.$ Using the recursive definition for $y_n,$ we end up getting $y_{M-1} = y_{M-1+z},$ so the claim holds for all $n \ge M - 1.$ In fact, we can continue this process to get that $M = 0,$ so the sequence is periodic in such a way that after one period, we go back to $x_0 = 1.$ Now extend the sequence backwards to indices $y_{-l} = y_{z-l}$ for $1 \le l \le m,$ where the $y_i$ still follow the recurrence. Clearly $y_{-1} = 1,$ and it can be shown using induction that $y_{-l} = 0$ for all $2 \le l \le m.$ This corresponds to $y_{z-2} = y_{z-3} = \dots = y_{z-m} = 0,$ giving $m - 1$ consecutive values of $y_n$ equal to $0.$ Thus $k \ge m - 1.$ Clearly if $k \ge m,$ then all of the $y_i$ must be $0$ at some point. Because of our period property, that means that all the $y_i$ are $0,$ contradicting $y_0 = 1.$ Therefore, we must have $\boxed{k = m - 1},$ as claimed at the beginning.

We first claim that there cannot be $m$ consecutive terms that are all divisible by $m$ (a direct consequence of this is that there cannot be more than $m+1$ consecutive terms that are all divisible by $m$. Suppose for the sake of contradiction that there are $m$ consecutive terms with $x_a, x_{a+1}, x_{a+2} \dots x_{a+m-1}$ such that $a > 0$ and $x_{a} \equiv 0 \pmod{m}, x_{a+1} \equiv 0 \pmod{m} \dots x_{a+m-1} \equiv 0 \pmod{m}$. Then note that $(x_{a-1} + x_{a} + x_{a+1} + \dots x_{a+m-2} \equiv x_{a+m-1}) \pmod{m} $. Thus $x_{a-1} + 0 + 0 \dots + 0 \equiv 0 \pmod{m}$. So it means that $x_{a-1} \equiv 0 \pmod{m}$. With similar reasoning, it follows that $x_{a-2} \equiv 0 \pmod{m}, x_{a-3} \equiv 0 \pmod{m}, x_{a-4} \equiv 0 \pmod{m} \dots x_{0} \equiv 0 \pmod{m}$. But we know that $x_0 \equiv 1 \pmod{m}$. It cannot possibly be true that $x_0 \equiv 0 \pmod{m}$. Thus, we know that our answer $k$ must obey $k \leq m-1$. Now we show that $k = m-1$ is obtainable, and once we have proven this, we have succesfully found our answer due to the upper bound we established. Suppose that we "extend" the sequence backwards. First define a new sequence $g_i = x_i \pmod{m}$ Then we would see that $g_{-1} \equiv 1 \pmod{m}, g_{-2} \equiv 0 \pmod{m}, g_{-3} \equiv 0 \pmod{m}, \dots g_{-m} \equiv 0 \pmod{m}, g_{-(m+1)} \equiv 1 \pmod{m}$. We just need to show that the terms $g_{-m}, g_{-(m-1)} \dots g_{-2}$ appear consecutively in that order later in the sequence. Note that due to the Pigeonhole principle, there exist positive integers $t, a, a+1, a+2, a+3 \dots a+m-1$ such that $g_{a} = g_{a+t}, g_{a+1} = g_{a+1+t}, g_{a+2} = g_{a+2+t} \dots g_{a+m-1} = g_{a+m-1+t}$. So $g_{a+b} = g_{a+t+b}$ where $b$ has the ability to take on negative values. So there is some future index $j$ such that $g_{j}, g_{j+1}, g_{j+2} \dots g_{j+m-1}$ where $g_{j} = g_{0}, g_{j+1} = g_{1}, g_{j+2} = g_{2} \dots $. The terms that come right before $g_{j}, g_{j+1}, \dots g_{j+m-1}$ mimic $x_{-1}, x_{-2}, x_{-3} \dots$. Hence, we have found $m-1$ consecutive terms that are $0 \pmod{m}$ and showed that there cannot be $m$ consecutive terms.

I claim that the answer is $m - 1$. Interpret everything following modulo $m$. Proof we cannot get $m$: Consider the first time we get $m$ zeroes in a row. Then reversing the relation forces the element before to also be zero, contradiction. Proof we get $m - 1$: Obviously, the sequence is periodic. Note that if we are given a block of $m$ elements, we can determine all the elements that come before it just by following the recursion, thus when we first see a block of $m$ elements appear twice, we know that going back some number of elements from the first block yields the starting conditions, so going back the same number of elements from the second block also yields the starting conditions, so the starting conditions appear periodically. Now reversing back from the starting conditions, we see that the $m$ elements before them are exactly $1, 0 , 0 \cdots 0$ where the $0$ is repeated $m - 1$ times.

$k \le n-1$ is true by contradiction, $k = n-1$ is true by proving periodic by PHP and looking at negative terms.