$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”.
-
- Let
$a_{i+1}=5i-1,$for$i=0,1,2,\ldots.$Find$a_5.$
- Let
-
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.