# Practice Paper 4 Question 16

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".

## Related topics

## Warm-up Questions

- Let \(a_{i+1}=5i-1,\) for \(i=0,1,2,\ldots.\) Find \(a_5.\)

## Hints

- Hint 1Why not compute a few terms with the rule given and see if you can spot any patterns?
- Hint 2Which indices of the sequence could you obtain with this method? Is there a pattern to these?
- Hint 3Conjecture a closed form solution for just these indices (part
*(a)*). Could you prove your conjecture? - Hint 4Have you considered proving your conjecture by induction?
- Hint 5Instead 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?\)
- Hint 6What about the other undefined terms? Can they be defined arbitrarily?
- Hint 7What restrictions are there on the choice of values for \(S_{4k+2}\) and \(S_{4k+3}\) terms?
- Hint 8What happens if \(S_{4k+3} = a = S_{4j+2}?\)
- Hint 9What values can't they take? Why?
- Hint 10Take \(S_{4k+2},\) there are two possible forms, but only one is valid. Could you determine which one it is?
- Hint 11Determine \(S_{4k+3}\) from \(S_{4k+2}.\)

## Solution

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{align}
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{align}
\] 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{align} S_{4k+2} &= 4k+ 4q+ 2\\ S_{4k+3} &= 4k-4q - 3 \end{align} \] 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.

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.[email protected]. Please do not write to this address regarding general admissions or course queries.