In the sequence $1, 0, 1, 0, 1, 0, 3, 5, \cdots$, each member after the sixth one is equal to the last digit of the sum of the six members just preceeding it. Prove that in this sequence one cannot find the following group of six consecutive members: \[0, 1, 0, 1, 0, 1\]
Problem
Source:
Tags: function, Recursive Sequences
18.06.2008 13:23
Actually every six consecutive terms(after the second term)couldn’t be in this type:$ a,b,a,b,a,b$ Note that $ x_i$ is unic number that $ 0\leq{x_i}\leq9$ and $ x_i = 2x_{i + 6} - x_{i + 7} \mod 10$ because: $ x_i + x_{i + 1} + x_{i + 2} + x_{i + 3} + x_{i + 4} + x_{i + 5} = x_{i + 6} \mod 10 \\ x_{i + 1} + x_{i + 2} + x_{i + 3} + x_{i + 4} + x_{i + 5} + x_{i + 6} = x_{i + 7} \mod 10 \\ \Longrightarrow{ x_i = 2x_{i + 6} - x_{i + 7} \mod 10}$ Therefore if $ x_i,x_{i + 1},x_{i + 2},x_{i + 3},x_{i + 4},x_{i + 5},a,b,a,b,a,b$ appearance in the sequence,then: $ x_i = x_{i + 2} = x_{i + 4} = 2a - b \mod 10 \\ x_{i + 1} = x_{i + 3} = x_{i + 5} = 2b - a \mod 10$ therefore the six concecutive terms which appearance before $ a,b,a,b,a,b$ is also in this type:$ c,d,c,d,c,d$ and the six concecutive terms which appearance before $ c,d,c,d,c,d$ is also in the same type and so on … contradiction!(note that the start of sequence is: $ 1,0,1,0,1,0,3,5,0,9,8,5,...$
26.09.2008 09:32
Actually, I think the above proof is flawed, because some of the indices are off by one. Working backwards from 0,1,0,1,0,1, I get the sequence would have to be $ \ldots, 2, 9, 2, 9, 9, 0, 1, 0, 1, 0, 1$, which doesn't match the pattern claimed. Here's my solution: Define the function $ Q(i) = 2 x_i + 4 x_{i+1} + 6 x_{i+2} + 8 x_{i+3} + 2 x_{i+5} \mod 10$. From the beginning of the sequence, compute $ Q(1) = 8$. Next, I claim that $ Q(i+1) = Q(i)$. To see this, we have: $ Q(i+1) = 2 x_{i+1} + 4 x_{i+2} + 6 x_{i+3} + 8 x_{i+4} + 2 x_{i+6} \mod 10$ $ = 2 x_{i+1} + 4 x_{i+2} + 6 x_{i+3} + 8 x_{i+4} + 2 (x_i + x_{i+1} + x_{i+2} + x_{i+3} + x_{i+4} + x_{i+5})$ $ \mod 10$ $ = 2 x_i + 4 x_{i+1} + 6 x_{i+2} + 8 x_{i+3} + 10 x_{i+4} + 2 x_{i+5} \mod 10$ $ = 2 x_i + 4 x_{i+1} + 6 x_{i+2} + 8 x_{i+3} + 2 x_{i+5} \mod 10$ $ = Q(i)$ We must therefore have $ Q(i) = 8$ for all $ i$. Now suppose that the sequence contained the terms "0, 1, 0, 1, 0, 1"; that is, there is some $ k$ so that $ (x_k, x_{k+1}, x_{k+2}, x_{k+3}, x_{k+4}, x_{k+5}) = (0,1,0,1,0,1)$. Then we compute $ Q(k) = 4$. But this is impossible; we conclude that "0, 1, 0, 1, 0, 1" never appears.
21.11.2008 17:53
juggle5 wrote: Actually, I think the above proof is flawed, because some of the indices are off by one. Working backwards from 0,1,0,1,0,1, I get the sequence would have to be $ \ldots, 2, 9, 2, 9, 9, 0, 1, 0, 1, 0, 1$, which doesn't match the pattern claimed. yes...you are right...sorry