Isl 2003 n1

by Wolstenholme, Aug 6, 2014, 7:27 PM

Let $m$ be a fixed integer greater than $1$ . The sequence $x_0$ , $x_1$ , $x_2$ , $\ldots$ is defined as follows:

$x_i= 2^i$ if $0 \leq i\leq m-1$ and $x_i = \sum_{j=1}^{m}x_{i-j},$ if $i\geq m$ .

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

Solution:

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.

Comment

0 Comments

Submit

glad to have found a fellow chipotle lover <3
by nukelauncher, Aug 13, 2020, 6:40 AM
the random chinese tst problem is the only thing I read, but I'll assume your blog is nice and give you a shout even though you probably never use aops anymoer
by fukano_2, Jun 14, 2020, 6:24 AM
wolstenholme - op
by AopsUser101, Jan 29, 2020, 8:27 PM
this blog is so hot
by mathleticguyyy, Jun 5, 2019, 8:26 PM
Hi. Nice Blog!
by User360702, Jan 10, 2019, 6:03 PM
helloooooo
by songssari, Jun 12, 2016, 8:21 AM
shouts make blogs happier
by briantix, Mar 18, 2016, 9:57 PM
You were just featured on AoPS's facebook page.
by mishka1980, Sep 12, 2015, 10:33 PM
This is late, but where is the ARML results post?
by donot, Aug 31, 2015, 11:07 PM
"I am Sam"
"Sam I am"
by mathwizard888, Aug 12, 2015, 9:13 PM
HW $\textcolor{white}{}$
by Eugenis, Apr 20, 2015, 10:10 PM
Uh-oh ARML practice is Thursday... I should start the homework.
by nosaj, Apr 20, 2015, 12:34 AM
Yes I am Sam, and Chebyshev polynomials aren't trivial, although they do make some problems trivial
by Wolstenholme, Apr 15, 2015, 10:00 PM
How are Chebyshev Polynomials trivial?
by nosaj, Apr 13, 2015, 4:10 AM
Are you Sam?
by Eugenis, Apr 4, 2015, 2:05 AM
@Brian: yes, yes I did #whoneedsalgskillz?

@gauss1181; hey!
by Wolstenholme, Mar 1, 2015, 11:25 PM
hello!!!
by gauss1181, Nov 27, 2014, 12:19 AM
Hi Wolstenholme did you actually use calc on that tstst problem
by briantix, Aug 2, 2014, 12:25 AM

18 shouts

Wolstenholme's blog

Isl 2003 n1

by Wolstenholme, Aug 6, 2014, 7:27 PM

0 Comments