# Show that any integer can be expressed as $S^{k}_{n}$

Consider the following sequence: $a_1=6$, $a_2=4$, $a_3=1$, $a_4=2$, and $a_n=a_{n-4}$ for $n \geqslant 5$.

Let $S^{k}_{n}$ be the sum of $k + 1$ elements from $a_n$ of the previous sequence. For example:

$S^{0}_{3} = 1 \\ S^{0}_{4} = 2 \\ S^{1}_{3} = 2 + 1 = 3 \\ S^{0}_{2} = 4 \\ S^{1}_{2} = 4 + 1 = 5 \\ … \\ S^{6}_{2} = 4 + 1 + 2 + 6 + 4 + 1 + 2 = 20 \\ … \\$

Show that any positive integer can be expressed as $S^{k}_{n}$.

This question was on an entrance exam for graduation. I wrote it from my memory, as the exam is not available online yet, maybe the wording is not 100% precise but I hope the examples are clear.

• I think you meant $S_2^6$ – 57Jimmy Jan 9 '18 at 21:12
• You're right, @57Jimmy, thanks! – rodorgas Jan 9 '18 at 21:15

As you notice, the sequence $a_n$ is by definition periodic: $6,4,1,2,6,4,1,2,6,4,1,2,...$

The sum of a whole "period" is $6+4+1+2=13$.

You can easily check that every number between $1$ and $12$ can be obtained as a sum of CONSECUTIVE numbers in the sequence $a_n$ (for instance, $9=1+2+6$). Then you just write any desired number $k$ (choose for example $k=139$) as a multiple of $13$ plus a number between $0$ and $12$ (in the example, $139 = 13 \cdot 10 + 9$). Then it just suffices to choose the right starting point and the right number of elements (in the example: to get $9$ you need to start at some $1$ in the sequence, so that you get $1+2+6=9$; for example, $S_3^{42} = 1+2+6+4+1+2+6+4+...+1+2+6= 13 \cdot 10 + 9 = 139$).

1. First, you can show exhaustively that you can produce every integer between 1 and 12. (See below.)
2. Then, note that the sum of any four consecutive elements in this sequence is 13: $S_n^3=13$.
3. Hence you can construct any other integer $N$ as follows:
• Let $S_n^k = N \pmod{13}$, which we have already shown you can construct.
• Every four additional terms we take, say $S_{n}^{k+4}$, adds 13 to our result: $$S_{n}^{k+4} = [N\pmod{13}] + 12, \qquad\qquad S_{n}^{k+4+4} = [N\pmod{13}] + 13+13,$$ and so on.
• So putting $\ell = \lfloor N/13\rfloor$, we find that $S_n^{k+4\ell} = N$.

Proof that you can produce every number between 1 and 12:

• 12 = 2 + 6 + 4
• 11 = 6 + 4 + 1
• 10 = 6 + 4
• 9 = 1 + 2 + 6
• 8 = 2 + 6
• 7 = 4 + 1 + 2
• 6 = 6
• 5 = 4 + 1
• 4 = 4
• 3 = 1 + 2
• 2 = 2
• 1 = 1
• Thanks. But is it 12 or should it be 13? $S_{n}^{k+4} = [N\pmod{13}] + 12$ – rodorgas Jan 9 '18 at 22:02