Let $r$ be a positive integer, and let $a_0 , a_1 , \cdots $ be an infinite sequence of real numbers. Assume that for all nonnegative integers $m$ and $s$ there exists a positive integer $n \in [m+1, m+r]$ such that \[ a_m + a_{m+1} +\cdots +a_{m+s} = a_n + a_{n+1} +\cdots +a_{n+s} \] Prove that the sequence is periodic, i.e. there exists some $p \ge 1 $ such that $a_{n+p} =a_n $ for all $n \ge 0$.
Problem
Source: IMO Shortlist 2013, Combinatorics #5
Tags: function, combinatorics, Additive combinatorics, Sequence, IMO Shortlist
mnbvmar
12.07.2014 12:33
Let's make the so-called failure function $P(i)$ defined as follows: it's length of the longest proper prefix (not equal to the whole sequence) of the sequence $(a_0,\dots,a_i)$ that is also its suffix; we call such subsequences borders. For example, if first 5 elements of the sequence are $(1,2,1,1,2)$, then $P(2)=1$, $P(3)=1$, $P(4)=2$. Let's also define a period of a finite sequence exactly as in the task, so that the longest period of sequence $(1,2,1,1,2)$ is $(1,2,1)$; last repetition of the period doesn't have to fit inside the word.
There are some known properties of $P(i)$:
1) $P(i+1) \le P(i) + 1$. That's obvious because if $k+1$ is the longest border of sequence $(a_0,\dots,a_{i+1})$, that is, $(a_0,\dots,a_k) = (a_{i-k+1},\dots,a_{i+1})$, then also $(a_0,\dots,a_{k-1})=(a_{i-k+1},\dots,a_i)$ and there exists a border of $(a_0,\dots,a_i)$ of length $k$; and there may be longer ones;
2) the shortest period of $(a_0,\dots,a_i)$ is $(i+1)-P(i)$. Let $k=P(i)$ and $p=i+1-k$ and assume our sequence has the shortest period equal to $p$. Then, according to the definition, $a_p=a_0$, $a_{p+1}=a_1$, ..., $a_i=a_{i-p}$. That means that $(a_p,a_{p+1},\dots,a_i)=(a_0,a_1,\dots,a_{k-1})$. This creates a 1-1 correspondence between periods and borders, especially between the shortest period and the longest border. Thus this statement follows.
Now that we know something about $P(i)$, let's make our task.
1. Take $s=0$. From the property in the task we conclude that for each nonnegative $m$ we have $a_m \in \{a_{m+1},\dots,a_{m+r}\}$. Now let's assume there are more than $r$ distinct values in $(a_i)$. Take any $r+1$ of them, let's say $b_1, b_2, \dots, b_{r+1}$; assume the latest first occurence among them is $a_m$. Let $i_1,i_2,\dots,i_{r+1}$ mark the latest occurence of $b_1,b_2,\dots,b_{r+1}$, respectively, in $(a_0,\dots,a_m)$. As all $i_1,\dots,i_{r+1}$ are distinct, there is one index $i_j$ for which $i_j \le m-r$. However, that means that $a_{i_j} \not\in \{a_{i_j+1},\dots,a_{i_j+r}\}$ - contradiction. The corollary is that there is a finite amount of continuous subsequences of length $x$ in $(a_0,\dots)$; in fact, there is no more than $r^x$ of them.
2. Note that the property in the task can be modified: for all nonnegative integers $m \leq s$ there is an integer $1 \le t \le r$ such that
\[ a_m + a_{m+1} + \dots + a_s = a_{m+t} + a_{m+t+1} + \dots + a_{s+t}. \]
By adding or subtracting elements having indices between $s$ and $m+t$, we derive that
\[ a_m + a_{m+1} + \dots + a_{m+t-1} = a_{s+1} + a_{s+2} + \dots + a_{s+t}. \]
It means that for any two indices $p,q$, there exist subsequences of equal length, not larger than $r$, beginning from these indices and having equal sum. Let's call this property $W(p,q)$
3. Let's assume we have two equal subsequences $(a_k,\dots,a_{k+r-1})$ and $(a_l,\dots,a_{l+r-1})$, $k<l$. Now from $W(k-1,l-1)$ we have that one of the following holds:
\[ a_{k-1} = a_{l-1} \]
\[ a_{k-1}+a_k = a_{l-1} + a_l \]
\[ \vdots \]
\[ a_{k-1}+a_k+\dots+a_{k+r-2} = a_{l-1}+a_l+\dots+a_{l+r-2} \]
However, all these equations reduce to $a_{k-1}=a_{l-1}$. It means that also $(a_{k-1},\dots,a_{k+r-1}) = (a_{l-1},\dots,a_{l+r-1})$. By repeating this procedure many times, we conclude that $(a_0,\dots,a_{k+r-1}) = (a_{l-k},\dots,a_{l+r-1})$. It means that $P(l+r-1) \geq k+r-1$.
4. There are no more than $r^r$ distinct connected subsequences of length $r$ in our sequence. By Dirichlet, in any interval of length $r^r+r$ there are $r^r+1$ subsequences and there must be a repetition; say these two repeated subsequences are distant by $d$ (it's difference between its first indices). Similarily, there are no more than $r^{r^r+r}$ subsequences of length $r^r+r$. Again by Dirichlet, there is a subsequence of length $r^r+r$ that appears infinitely many times. This subsequence has a repetition having distance equal to $d$, which means there are infinitely many pairs of equal subsequences of length $r$ distant by $d$. By (3.) we follow that for infinitely many indices $c_0,c_1,c_2,\dots$ we have $P(c_i) \geq c_i-d$.
5. Note $Q(x) = x-P(x)$. Of course by definition $Q(x) \ge 0$ and. using the first property of $P(i)$, $Q(x+1) \ge Q(x)$. Then for infitiely many indices $c_0,c_1,\dots$ we have $Q(c_i) \le d$. By Dirichlet, there is a value $d_0\in\{0,\dots,d\}$ and infinitely many indices $e_0,e_1,\dots$ for which $Q(e_i) = d_0$. Now see that for any $i \ge 0$ we have
\[ Q(e_i) \ge Q(e_i+1) \ge Q(e_i+2) \ge \dots \ge Q(e_{i+1}). \]
However $Q(e_i)=Q(e_{i+1})$. We follow that for each $j \ge e_0$ we have $Q(j) = d_0$.
6. Now we use second property of $P(i)$: subsequence $(a_0,\dots,a_i)$ has the shortest period of length $Q(i)+1$. A final note: for each $j \ge e_0$ subsequence $(a_0,\dots,a_j)$ has period of length $d_0+1$. It means that also the infinite sequence has such period!
Note I proved that the period length $p \le r^r+1$. There should be a better, cleaner and faster solution
The solution exploits the fact that if $(a_k,\dots,a_{k+r-1}) = (a_l,\dots,a_{l+r-1})$, then also $(a_0,\dots,a_{k+r-1}) = (a_{l-k},\dots,a_{l+r-1})$. This has much to do with failure function of KMP algorithm (and prefixes that are also the suffixex of finite sequences). If we find infinitely many such pairs of sequences having the same distance between each other, we can also find a period of the infinite sequence.
antimonyarsenide
16.07.2014 02:26
A similar (but much shorter, it seems) argument can be found on my blog here EDIT: Actually, I might as well repost it here so people don't have to go through the link:
First note there can be at most $r$ distinct values of $a_i$ (each eventually appears in every $r$-length block), so by pigeonhole, among any $r^r+1$ consecutive $r$-strings there are two that are identical. Consider two such strings, say the ones beginning at $a_n$ and $a_{n+k}$, where we pick $n=n_0>2*(r^r+1)$. Setting $s=k$ in the problem condition then gives that $a_{n-1}+\cdots+a_{n+k-2}=a_{n+j}+\cdots+a_{n+j+k-1}$ for some $0\leq j \leq r-1$. But $a_{n+k}+\cdots+a_{n+j+k-1}=a_{n}+\cdots+a_{n+k-1}$ by the identical $r$-strings, so we get $a_{n-1}=a_{n+k-1}$. Iterating backwards, we get that the sequence is periodic mod $k$ up to $a_{n+k+r-1}$.
Now let's repeat this process for a different $n=n_1>2*(r^r+1)$, getting that the elements from $a_0$ to $a_{2*r^r+1}$ have to be periodic mod another $k'<r^r+1$. If $k'\neq k$, the results of the disagreement would be visible within two periods of the larger one, so we have $k'=k$.
But we can pick $n_1$ arbitrarily large to get that the sequence is always periodic mod $k$.
dgrozev
19.07.2014 17:02
The same idea, but a little bit different point of view and balance. Let's restate the given condition: For each $m,n$ there exists $s, 0\le s < r$, such that \[ a_m+a_{m+1}+\ldots +a_{m+s}=a_n+\ldots + a_{n+s}\,\,\,\,\,\,\,\, \text{(1)} \] We call a pattern every succession of $r-1$ members of the given sequence $a_{i+1},a_{i+2},\ldots, a_{i+r-1} $. Now the key observation. If there exist two equal patterns then the sequence is periodic up to the second one. Indeed if $a_{n+i}=a_{m+i}\,, i=1,2,\ldots,r-1\,,\, n<m$ , by (1) we consecutively get $a_n=a_m,a_{n-1}=a_{m-1},\ldots$ This fact motivates us to check that there are finitely many different values of $a_i$. Indeed if it's true, the number of different patterns will be finite and in every sufficiently big interval there will be two equal patterns. To prove it, note that for each $a_i$ there exists $a_j\,, 0<j-i\le r $ with $a_i=a_j$. It is obvious if we apply (1) to $m=i,n=i+1$. Thus, for each $N$, amongst $a_i, a_{i+1},\ldots, a_{i+N}$ there are at least $\lfloor \frac{N}{r}\rfloor$ terms equal to $a_i$. Now, if we assume there are more than $r$ pairwise different members of the sequence, this argument easily brings us to contradiction, since we could allocate too many terms of the sequence in some sufficiently big interval.
antimonyarsenide
19.07.2014 18:27
dgrozev wrote: Let's restate the given condition: For each $m,n$ there exists $s, 0\le s < r$, such that \[ a_m+a_{m+1}+\ldots +a_{m+s}=a_n+\ldots + a_{n+s}\,\,\,\,\,\,\,\, \text{(1)} \] Sorry, how is this equivalent to the given condition? Are you assuming $n \in [m+1, m+r]$? Even then I don't see why the equivalence is immediate...
dgrozev
19.07.2014 20:09
Well, take $m,n\,, m<n$ and apply the original condition to $a_m+a_{m+1}+\ldots + a_{n-1}$. Depending whether the terms in the second sum intersect with the first one, just remove the repeating ones or add some new ones to both sums to get the second condition.
ComboCracker
30.12.2016 22:17
Quote: So we are clearly done from this point. Elaborate?
FE_Eliminator
31.12.2016 02:27
Okay by taking $s=0$, we can see that in any 2 consecutive r-blocks, there can be at most $r$ distinct values and every distinct value in one $r$ block must appear in the next one. So there are at most $k$ distinct values where $k \leq r$ and eventually every r-block will contain these $k$ values. (Note that if $k=r$ this problem is solved). Now let's make a slight trivial adjustment to what we're allowed to do. If $n$ is greater than $r$, the identity given becomes for any $m$ and $n>r$, there exists some $s<r$ in which $a_{n}$ to $a{n+s}$ equals $a_m$ to $a_{m+s}$ for any $m$ and $n$. Now immediately we know that by Schubfachprinzip we have 2 congruent r-blocks in a finite interval. Call the two intervals $[n_1, n_1+r]$ and $[n_2, n_2+r]$ If we let $m=n_1-1$, and $n=n_2-1$ and keep repeating this process in a similar fashion backwards, we get that the entire sequence is periodic up to $n_2+r$ with a period of $n_2-n_1$ So we are clearly done from this point.
SmartClown
24.03.2017 03:47
Setting $s=0$ yields that for every $m$ there exists $1 \le i \le r$ such that $a_m=a_{m+i}$, so if more than $r$ numbers appeared in the sequence we would have that at some $r$-interval there are $r+1$ numbers, contradiction. Now we proved there are at most $r$ numbers. By taking any $r^r+1$ consecutive $r$-intervals, we see that there must be two which are the same. Also let those intervals begin at $a_k$ and $a_l$, $l>k$. It is trivial that $l-k$ can take only finitely many values, so let $l-k=p$, where difference $p$ appears infinitely many times . Taking $m=k-1$ and $s=k+p-2$ immediately gives $a_{k-1}=a_{l-1}$. By continuing this process we get that our sequence is $p$-periodic up to $a_l$. Since difference $p$ appears infinitely many times, we conclude that our sequence is $p$-periodic too, so we are finished.
stroller
02.10.2018 03:26
Does the problem statement still hold when $s$ can only take on values in $\mathbb{N}$?
william122
28.04.2020 05:17
Solution with MathStudent2002 We can rephrase the condition as: For all pairs $(i,j)$, there exists $k\in[0,r)$ such that $a_i+\ldots+a_{i+k}=a_j+\ldots+a_{j+k}$. However, there exists no such $k$ if $a_i\neq a_j$, $a_{i+s}=a_{j+s}\forall 0<s<r$. Thus, we can't have two blocks of $r$ consecutive elements which only differ in the first term. Now, consider $i\neq j$ such that $a_{i+s}=a_{j+s}\forall 0\le s<r$, which is possible since there are only a finite number ($r^r$) of possible blocks of r consecutive elements. By our previous argument, we must have $a_{i-1}=a_{j-1}$, which in turn implies $a_{i-2}=a_{j-2}$, and continuing downwards we get that $a_k=a_{k+(i-j)}\forall k\le j$. So, the sequence is periodic before $\max(i,j)$. However, since we can find arbitrarily large $(i,j)$ with this property, we must have that the sequence is entirely periodic, as desired.
SnowPanda
05.05.2020 03:41
First, let $$S_k(i) = a_i + a_{i + 1} + \ldots + a_{i + k - 1}$$be the sum of the $k$ consecutive terms starting with $a_i.$ Then the condition means for every $k \geq 1$ and every $m \geq 0,$ there exists $n \in [m + 1, m + r]$ with $S_k(m) = S_k(n).$
Claim: For each $k \geq 1,$ there are at most $r$ distinct values in the list $S_k(i)$ for $i = 0, 1, 2, \ldots.$
Proof: Assume that for some value of $k,$ there are at least $r + 1$ distinct values. Consider the first $r + 1$ such values to appear, and take $m$ such that for each of these values $x,$ there is some $i < m$ with $S_k(i) = x$ (so each of these $r + 1$ values has appeared before $m$). Then consider $$S_k(m), S_k(m + 1), \ldots, S_k(m + r - 1).$$There are at most $r$ values in this list, so there is at least one $x$ of those first $r + 1$ values which is not in this list. Consider the largest $i < m$ such that $S_k(i) = x,$ which must exist since there is at least one such $i.$ Then there is no $j$ with $i + 1 \leq j \leq m + r - 1$ and $S_k(j) = S_k(i),$ which is a contradiction (as $i + r \leq m + r - 1$). So there can be at most $r$ distinct values.
Now let $n = r^{2r} + 1.$ For each $1 \leq k \leq n,$ let $M_k$ be the last index where a new value appears in the list $S_k(i),$ meaning the greatest $i$ such that $S_k(i) \neq S_k(j)$ for all $0 \leq j < i.$ (This must exist since there can be at most $r$ such indices $i$.) Let $M = \max(M_1, \ldots, M_n) + 1,$ so then for all $1 \leq k \leq n,$ any value in the list $S_k(i)$ appears at some $i < M.$
Claim: There exists some $k$ with $1 \leq k \leq n,$ and some $m \geq M,$ for which $S_k(m) = S_k(m + 1) = \ldots = S_k(m + r).$
Proof: Consider the lists $S_k(M), S_k(M + 1), \ldots, S_k(M + r)$ for each $1 \leq k \leq n.$ We will show that two of these lists differ by a constant.
First, note that for any $i$ and $k,$ $$S_k(i + 1) - S_k(i) = a_{i + 1} + \ldots + a_{i + k} - (a_i + \ldots + a_{i + k - 1}) = a_{i + k} - a_i.$$Since there are at most $r$ distinct values in $a_0, a_1, \ldots,$ there are at most $r^2$ possible values for this (over all $i$ and $k$).
For each $1 \leq k \leq M,$ consider the sequence of differences between consecutive terms, $S_k(M + 1) - S_k(M), S_k(M + 2) - S_k(M + 1), \ldots, S_k(M + r) - S_k(M + r - 1).$ There are $r$ terms in this sequence, and each term must be one of the at most $r^2$ possible values, so then there are at most $(r^2)^r = r^{2r}$ distinct sequences possible. Since we have $n = r^{2r} + 1$ such sequences, at least two must be the same. Suppose these are at $k_1$ and $k_2,$ with $k_1 > k_2.$
Then we have $S_{k_1}(i + 1) - S_{k_1}(i) = S_{k_2}(i + 1) - S_{k_2}(i)$ for all $M \leq i \leq M + r - 1.$ This implies $S_{k_1}(i + 1) - S_{k_2}(i + 1) = S_{k_1}(i) - S_{k_2}(i)$ for all $M \leq i \leq M + r - 1,$ so then $$S_{k_1}(i) - S_{k_2}(i) = c$$for all $M \leq i \leq M + r$ and some constant $c.$
However, we have
\begin{align*}
S_{k_1}(i) - S_{k_2}(i) &= a_i + \ldots + a_{i + k_1 - 1} - (a_i + \ldots + a_{i + k_2 - 1}) \\
&= a_{i + k_2} + \ldots + a_{i + k_1 - 1} \\
&= S_{k_1 - k_2}(i + k_2).
\end{align*}
So then we have $$S_{k_1 - k_2}(i + k_2) = c$$for all $M \leq i \leq M + r.$ Taking $k = k_1 - k_2$ (so $0 < k < n$) and $m = M + k_2$ (so $m > M$), we have $S_k(m) = S_k(m + 1) = \ldots = S_k(m + r).$
Claim: For the $k$ from the previous claim, $S_k(i)$ is constant (for all $i \geq 0$).
Proof: We know $S_k(m) = \ldots = S_k(m + r)$ is some constant $c.$ If there is some $i < m$ with $S_k(i) \neq c,$ then we get a contradiction by taking the greatest such $i,$ as then there is no $i < j < m$ or $m \leq j \leq m + r$ with $S_k(i) = S_k(j).$ So then $S_k(i) = c$ for all $i \leq m.$ However, we have $m \geq M,$ and all values in the sequence $S_k(i)$ must appear for some $i < M,$ as we chose $M$ to come after the first occurrence of any value in the list. So there can be no values other than $c$ in the list, so $S_k(i) = c$ for all $i > m$ as well.
So then we have $S_k(i + 1) - S_k(i) = 0$ for all $i \geq 0.$ However, $S_k(i + 1) - S_k(i) = a_{i + k} - a_i,$ so this means $a_{i + k} = a_i$ for all $i \geq 0,$ so the sequence is periodic.
NoctNight
23.05.2022 15:32
Lemma: The sequence $a_0,a_1,\cdots$ takes $l$ distinct values, where $l\leq r$.
Proof: Taking $s=0$ shows that for all nonnegative integers $m$, there exists $n\in [m+1,m+r]$ such that $a_m=a_n$. For each $i$, f we draw rays from $a_i$ to $a_j$ where $j>i$ is the smallest index such that $a_i=a_j$ - extend this process infinitely so we have some number of rays that are a partition of $\mathbb Z$. Notice that each of the rays have density at least $\frac{1}{r}$ in $\mathbb Z$ because the consecutive differences are at most $k$ as $n\in [m+1,m+r]$. Then, FTSOC, if there are $l>r$ distinct values, meaning that there are $l>r$ distinct rays, then the total density of the rays (since density is additive) is greater or equal to $\frac{l}{r}>1$. But the rays are a partition of $\mathbb Z$, which has density $1$, a contradiction.
Rewrite the condition as: For each pair of nonnegative integers $m,s$, there exists $n\in [m+1,m+r]$ such that
$$a_m+\cdots+a_{n-1}=a_{m+s+1}+\cdots+a_{n+s}$$by adding or subtracting the terms between $a_n$ and $a_{m+s}$ from both sides. We denote the assertion of the above statement as $P(m,m+s+1)$.
Claim: There exists some constant $C$ and infinitely many positive integers $M$ such that for each $M$, $a_n=a_{n+p_M}$ for all $0\leq n\leq M$ for some positive integer $p_M<C$.
Proof: Let $v_{i,k}$ denote the ordered $(k+1)$-tuple $(a_i,\cdots,a_{i+k})$. We fix some arbitrary $k\geq r$; notice that the set $S=\{v_{i,k}\mid i=0,1,2,\cdots\}$ is finite as there are at most $l$ values attained by $\{a_i\}_{i\geq 0}$ so there are at most $l^{k+1}$ different values of $v_{i,k}$. Then for any $t$, by PHP, two $(k+1)$-tuples in the set $\{v_{t,k},v_{t+1,k},\cdots,v_{t+l^{k+1},k}\}$ that are the same; take these two tuples to be $v_{c,k}$ and $v_{d,k}$. Then we have $a_i=a_{i+d-c}$ for $c\leq i\leq c+k$.
We wish to show inductively that if $a_i=a_{i+d-c}$ for $x\leq i\leq c+k$, then $a_{x-1}=a_{x-1+d-c}$. The assertion $P(x-1,x-1+d-c)$ shows $$a_{x-1}+\cdots+a_{x-1+n-1}=a_{x-1+d-c}+\cdots+a_{x-1+d-c+n-1}$$By the inductive assumption, since $c+k-x>c+k-c=k>r$, we have $a_i=a_{i+d-c}$ for all $x\leq i\leq x-1+n-1$ so this gives $a_{x-1}=a_{x-1+d-c}$, as desired. This establishes that the period $p_M=d-c<l^{k+1}$ for some fixed $k>r$, so we take $C=l^{k+1}$. Then take $M=c+k$, of which there exists infinitely many of by taking infinitely many $t$.
Since $p_M$ attains finitely many values and there are infinitely $M$, some value of $p_M$ is attained infinitely many times - let this value be $p_M=p$. Then, FTSOC, if some $n$ satisfies $a_n\neq a_{n+p}$, take $M'>n$ such that $p_{M'}=p$, implying $a_n=a_{n+p}$, a contradiction. Hence, we have $a_n=a_{n+p}$ for all $n\geq 0$.
NoctNight
23.05.2022 15:34
william122 wrote: Solution with MathStudent2002 We can rephrase the condition as: For all pairs $(i,j)$, there exists $k\in[0,r)$ such that $a_i+\ldots+a_{i+k}=a_j+\ldots+a_{j+k}$. However, there exists no such $k$ if $a_i\neq a_j$, $a_{i+s}=a_{j+s}\forall 0<s<r$. Thus, we can't have two blocks of $r$ consecutive elements which only differ in the first term. Now, consider $i\neq j$ such that $a_{i+s}=a_{j+s}\forall 0\le s<r$, which is possible since there are only a finite number ($r^r$) of possible blocks of r consecutive elements. By our previous argument, we must have $a_{i-1}=a_{j-1}$, which in turn implies $a_{i-2}=a_{j-2}$, and continuing downwards we get that $a_k=a_{k+(i-j)}\forall k\le j$. So, the sequence is periodic before $\max(i,j)$. However, since we can find arbitrarily large $(i,j)$ with this property, we must have that the sequence is entirely periodic, as desired. I think that the condition you have proved (there are infinitely many $M$ such for each $M$, there exists $p$ that $a_n=a_{n+p}$ for all $n\leq M$) is not sufficient to imply the entire sequence is periodic (for example, the sequence $a_n=\nu_2(n)$ satisfies the condition you have proven, but is not periodic).
Inconsistent
11.10.2022 21:13
Are you kidding me. Let $P_i$ be the set of partial sums of length $i$ sequences. Let $S_i$ be the set of differences of $P_i$. Notice that $S_1 \cup S_2 \cup S_3 \cup \cdots$ is finite since its element's magnitudes are bounded above by $r(\max S_1)$. Hence if each $P_i = \{s_{i_1} < s_{i_2} < \cdots s_{i_k}\}$ for $k \leq r$, then there are finitely many ways to assign $k \leq r$ and $s_{i_2}-s_{i_1}, s_{i_3}-s_{i_2}, \ldots, s_{i_k}-s_{i_{k-1}} \in S_1$, hence by we must have by infinite pigeonhole that there is an infinite set $P'$ where $P_i$ is identical up to a shift for all $i \in P'$. Once again, by infinite pigeonhole, there exist $i, j \in P'$ such that the sequence of partial sums of length i and the sequence of partial sums of length j are identical up to the $r$th element, up to a shift. This means the sequence of partial sums of length $|j - i|$ has a consecutive sequence of $r$ identical values, hence the sequence of partial sums of length $|j - i|$ have constant value everywhere by the condition. Thus, it is obvious by taking differences of consecutive partial sums of length $|j-i|$ that the original sequence has period that at most $|j - i|$, finishing.