The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field.

The Computer Laboratory

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

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

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

Hints

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