How do I find a recurrence relation?

Question

Let n1, n2, . . . , n100 be a sequence of integers. Initially, n1 = 1, n2 = −1 and all the other numbers are 0. After every second, we replace the kth term of the sequence with the sum of the kth and (k+1)th term for k = 1, 2, . . . , 99, and replace the 100th term with the sum of the 100th and 1st term. (All of this is done simultaneously, so each new term is the sum of two terms of the sequence from before any replacements.) How do I show that for any integer "I", there is some index k and some time t for which the absolute value of the kth term of this sequence is larger than I at time t. I'm trying to find a recurrence relation in the sequence, but can't find a way to finish.

Answer 1

Instead of indexing your $n$s by $1,\ldots,100$ it is neater to index them by residue classes modulo $100$; then the update operation can be described uniformly as "add to each position the number formerly immediately to the left of it".

If we write the value of $n_k$ at time $t$ as $n_k[t]$, the recurrence is simply $$ n_k[t+1] = n_k[t] + n_{k+1}[t] $$ where we must remember to treat the subscripts modulo 100.

Apart from that, it is a nice and linear recurrence which you should recognize as the recurrence for Pascal's triangle, though mirrored so it grows to the left of the initial column. Once the lines get wider than $100$ elements we simply add up columns at a distance of 100 in the triangle.

Since the recurrence is linear, the effect of the initial $1$ and the effects of the initial $-1$ can be handled separately from each other, and we get something like $$ n_k[t] = b_{1-k}[t] - b_{2-k}[t] \qquad\text{where } b_k[t] = \sum_{j\equiv k\pmod{100}} \binom{t}{j}$$

Hint for the rest of the problem: choose $t$ to be a prime $\gg I$. Then each $b_k[t]$ is a multiple of $t$, except that two of them are increased by $1$. But they can't all be the same multiple of $t$, because $100a+2$ cannot equal $2^p$ ...