3
$\begingroup$

Say we have $100$ terms connected in a circle, starting with $x_1$ and going clockwise to $x_2$, to $x_3$, etc. and with $x_{100}$ going to $x_1$. Now initially $x_1 = 1$ and $x_2=-1$ and the rest of the terms are $0$. What happens when we a apply a rule where each $x_i$ simultaneously becomes the sum of itself and the term to its left? (for example $x_1\mapsto x_1+x_2$) Will the terms grow without bound? How can I prove it?

I attempted to observe what happens when there are only $4$ terms \begin{matrix} &&a_{1} \\ &\swarrow && \nwarrow \\ a_{4}&&&&a_{2}\\ &\searrow&&\nearrow\\ && a_3 \end{matrix}

and on every other iteration of the rule I see that there is a pair of terms opposite each other which equal powers of two. Does this tell me anything about the case with $100$ terms? or in general with $n$ terms?

$\endgroup$
  • 3
    $\begingroup$ 1) Do you mean that simultaneously you apply this rule to all elements? 2) The picture suggests that you apply the same rule to the last element, wrapping around back to the first element; however the title suggests otherwise. $\endgroup$ – vadim123 Dec 24 '15 at 20:33
  • $\begingroup$ @vadim123 sorry, yes I want the rule to be applied simultaneously to each term, the $n$th term too. I edited it $\endgroup$ – G.host163 Dec 24 '15 at 20:49
  • $\begingroup$ This question is very similar to Problem 5 of the current round of the USAMTS. The deadline for submitting solutions is January 4th. $\endgroup$ – JimmyK4542 Dec 25 '15 at 4:16
3
$\begingroup$

Let $x_{i,j}$ be the $i$-th term after $j$ operations . Let also $x_{i,0}=x_i$

It's not hard to prove using induction that :

$$x_{i,j}=\sum_{k=0}^{j} \binom{j}{k} x_{i+k}$$ where we make the convention that $x_{n+l}=x_l$ for $l \geq 1$ .

This can be seen by looking for patterns :

$$x_{k,1}=x_k+x_{k+1}$$ $$x_{k,2}=x_{k,1}+x_{k+1,1}=x_k+2x_{k+1}+x_{k+2}$$ $$x_{k,3}=x_{k,2}+x_{k+1,2}=x_k+3x_{k+1}+3x_{k+2}+x_{k+3}$$ which looks a lot like Pascal's triangle and then to prove it it's easy .

Also notice that most of the terms in the summation will be $0$ so now all the terms will look like this :

$$x_{s,j}=\binom{j}{n+1-s}-\binom{j}{n+2-s}+\binom{j}{2n+1-s}-\binom{j}{2n+2-s}+\ldots$$ (this is for $s>2$ . )

For $s=1$ there's also $\binom{j}{0}-\binom{j}{1}$ in the sum and for $s=2$ there's a $-\binom{j}{0}$ in the sum.

Now you need to choose that $j$ carefully to get a big (or small) sum.

I'll let you handle the remaining details (which seem pretty complicated )

EDIT :

I'll explain the induction :

For $j=1$ it's just : $$x_{i,1}=x_i+x_{i+1}=x_i \binom{1}{0}+x_{i+1} \binom{1}{1}$$

Assume that it's true for some $j$ and then prove it for $j+1$ :

We know that :

$$x_{i,j+1}=x_{i,j}+x_{i+1,j}$$

We also know that :

$$x_{i,j}=\sum_{k=0}^{j} \binom{j}{k} x_{i+k}$$ $$x_{i+1,j}= \sum_{k=0}^{j} \binom{j}{k} x_{i+1+k}=x_{i+j+1}\binom{j}{j}+\sum_{k=1}^{j} \binom{j}{k-1} x_{i+k}$$

Now group the terms and use Pascal's theorem :

$$x_{i,j+1}=x_{i,j}+x_{i+1,j}=\sum_{k=0}^{j} \binom{j}{k} x_{i+k}+x_{i+j+1}\binom{j}{j}+\sum_{k=1}^{j} \binom{j}{k-1} x_{i+k}=x_i+x_{i+j+1}+\sum_{k=1}^{j} x_{i+k} \left ( \binom{j}{k}+\binom{j}{k-1} \right )=x_i \binom{j+1}{0}+x_{i+j+1} \binom{j+1}{j+1} + \sum_{k=1}^{j} x_{i+k} \binom{j+1}{k}=\sum_{k=0}^{j+1} \binom{j+1}{k}x_{i+k}$$ QED .

$\endgroup$
  • $\begingroup$ Can you elaborate on the induction part? I tried it but got stuck after writing $x_{ik}$ and $x_{i+1,k}$ as series $\endgroup$ – G.host163 Dec 25 '15 at 2:49
  • $\begingroup$ I don't think your formula for $s=1$ and $s=2$ is correct. In the example with $4$ terms I got that $x_{1,4}=-2 \ne \binom40- \binom41$ $\endgroup$ – mysatellite Dec 25 '15 at 4:12
  • $\begingroup$ @Sky The formula is right . You just forgot the term $\binom{4}{4}$ . It should be : $$x_{1,4}=\binom{4}{0}-\binom{4}{1}+\binom{4}{4}=-2$$ $\endgroup$ – user252450 Dec 25 '15 at 7:36
  • $\begingroup$ @ComplexPhi Oh I see so you meant for $s=2$ the first two terms in the series is different $\endgroup$ – mysatellite Dec 25 '15 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.