Let $S_i$ be a sequence of integers obeying ${S}_{({S_i}+5)}=i-1,$ for $i=0,1,2,\ldots$ and $S_0=0.$ Give a non-recursive expression for (a) one such sequence $S_i,$ (b) all possible such sequences $S_i.$ Different expressions for different subsets of $i=0,1,\ldots$ are allowed, e.g. “$i$ is odd” or “$i$ is even”.
  1. Let $a_{i+1}=5i-1,$ for $i=0,1,2,\ldots.$ Find $a_5.$

Why not compute a few terms with the rule given and see if you can spot any patterns?

Which indices of the sequence could you obtain with this method? Is there a pattern to these?

Conjecture a closed form solution for just these indices (part (a)). Could you prove your conjecture?

Have you considered proving your conjecture by induction?

Instead of the usual $P_n \implies P_{n+1},$ how about trying $P_n \implies Q$ and $Q \implies P_{n+1},$ where both implications are obtained from the rule for $S_i?$

What about the other undefined terms? Can they be defined arbitrarily?

What restrictions are there on the choice of values for $S_{4k+2}$ and $S_{4k+3}$ terms?

What happens if $S_{4k+3} = a = S_{4j+2}?$

What values can’t they take? Why?

Take $S_{4k+2},$ there are two possible forms, but only one is valid. Could you determine which one it is?

Determine $S_{4k+3}$ from $S_{4k+2}.$

Denote the condition ${S}_{({S_i}+5)}=i-1$ with $(*).$

We want to define a sequence $S_i$ such that $(*)$ holds. Let’s look at which terms are actually determined: starting from $S_0 = 0$ we get that $S_{S_0 + 5} = S_5 = -1.$ Then $S_{S_5 + 5} = S_4 = 4$ and $S_{S_4 + 5} = S_9 = 3.$ We can continue this process to get $S_8=8,$ $S_{13}=7,$ $S_{12}=12$ and so on.

$S_0$ $S_1$ $S_2$ $S_3$ $S_4$ $S_5$ $S_6$ $S_7$ $S_8$ $S_9$ $S_{12}$ $S_{13}$
$0$ $?$ $?$ $?$ $4$ $-1$ $?$ $?$ $8$ $3$ $12$ $7$

We notice that this method only gives us values for $S_{4k}$ and $S_{4k+1},$ with the exception of $S_1.$ We could conjecture a possible solution for part (a) that $S_{4k}=4k$ and $S_{4k+1}=(4k+1)-6=4k-5.$ By our conjecture, $S_1=-5$ from which follows that $S_0=0$ as given. Hence, we try to prove our conjecture in Proof 1 below.

In order to come up with a generalised solution for part (b), we need to specify values for $S_{4k+2}$ and $S_{4k+3}$ to define the full sequence $S_n.$ To obtain these, we can try some arbitrary values, but we may discover many cause contradictions with earlier results. We must realise that the subsequences $S_{4k+2}$ and $S_{4k+3}$ must not overlap, and that $S_{4k+2}$ and $S_{4k+3}$ cannot be of the form $4j$ or $4j+3$ (see Proof 2 below). We can choose $S_{4k+2}$ to be any $4j +1 = 4k + 4q + 1$ or any $4j + 2 = 4k + 4q + 2,$ for a fixed $q \in \mathbb{Z}.$ If $S_{4k+2} = 4k + 4q + 1$ then: $$ \begin{aligned} 4k+ 1 \overset{(\ast)}{=} S_{S_{4k+2} + 5} &= S_{4k+ 4q + 6} \\&= S_{4(k+1) + 4q + 2} \\&= 4(k+1+q) + 4q + 1 \\&= 4k + 8q + 5 \end{aligned} $$ from which we must have $1 = 8q + 5,$ which has no integer solutions.

So we have to pick $S_{4k+2} = 4k+ 4q+ 2.$ Then, applying $(\ast)$ we determine $S_{4k+3}$ as well: $$ 4k+ 1\overset{(\ast)}{=} S_{S_{4k+2} + 5} = S_{4k+4q+7} = S_{4(k+1) + 4q + 3} $$ So to obtain $S_{4k+3},$ we substitute $k-q-1$ for $k$ to obtain $S_{4(k-q-1+1) + 4q + 3} = S_{4k+3}$ $= 4(k-q-1)+1.$ Hence the only valid solutions are: $$ \begin{aligned} S_{4k+2} &= 4k+ 4q+ 2\\ S_{4k+3} &= 4k-4q - 3 \end{aligned} $$ where $q \in \mathbb{Z}$ is arbitrary. This gives us the general solution:

$$ S_i = \begin{cases} i &\text{ if } i \equiv 0 \mod 4 \\ i - 6 &\text{ if } i \equiv 1 \mod 4 \\ i + 4q &\text{ if } i \equiv 2 \mod 4 \\ i - 6 - 4q &\text{ if } i \equiv 3 \mod 4 \end{cases} $$

Proof 1

We can show this by first assuming $S_{4k+1}=4k-5,$ from which we deduce that ${S}_{({S_{4k+1}}+5)}={S}_{(4k-5+5)}=S_{4k}.$ And then from $(*)$ we know ${S}_{({S_{4k+1}}+5)}=4k,$ which shows that $S_{4k+1}=4k-5 \implies S_{4k}=4k.$

Next, we assume $S_{4k}=4k,$ from which we can deduce $S_{(S_{4k}+5)}=S_{4k+5}=S_{4(k+1)+1}.$ And from $(*)$ we know that $S_{(S_{4k}+5)}=4k-1=4(k+1)-5,$ which shows that $S_{4k}=4k \implies S_{4(k+1)+1}=4(k+1)-5.$ By (slightly convoluted) induction, we have proven our conjecture.

Proof 2

First of all, we must choose the sets $\{t : t = S_{4k+2} \text{ for } k \in \mathbb{Z} \}$ and $\{t : t = S_{4k+3} \text{ for } k \in \mathbb{Z} \}$ to be disjoint. If $S_{4k+3} = a = S_{4j + 2}$ then $S_{S_{4k+3} + 5} = 4k+2$ and $S_{S_{4j+2} + 5} = 4j+1.$ By $(\ast)$ both of these values must be equal to $S_{a + 5},$ which is a contradiction.

Secondly, for every $k$ we must have that $S_{4k+2}, S_{4k+3} \notin \{t : t \equiv 0 \mod 4 \} \cup \{ t : t \equiv 3$ $\mod 4\}.$ Take the $S_{4k+2}$ case: if $S_{4k+2} = 4j$ then $4k+1 \overset{(\ast)}{=} S_{S_{4k+2} + 5}$ $= S_{4j+5} = S_{4(j+1) + 1}.$ By the above, this final term is equal to $4\big((j+1) -1\big) - 1 = 4j -1$, which cannot equal $4k+1.$ Similarly if $S_{4k+2} = 4j+3$ then $4k+1 \overset{(\ast)}{=} S_{S_{4k+2} + 5} = S_{4(j+1)}$, which by the above is equal to $4(j+1).$ Once again, we obtain a contradiction. The $S_{4k+3}$ case is similar.