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. # 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 . Please do not write to this address regarding general admissions or course queries.