Starting with any non-zero natural number, it is always possible to form a sequence of numbers that ends in 1, by repeatedly following the instructions below:

- if the number is odd, add 1;
- if the number is even, divide by 2.

For example, starting with the number 21, the following sequence is formed:

$$
21 \rightarrow 22 \rightarrow 11 \rightarrow 12 \rightarrow 6 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 1
$$

This sequence contains nine numbers; therefore, we say it has a length of 9. Additionally, since it starts with an odd number, we say it is an odd sequence.

a) Write the sequence that starts with 37.

b) There are three sequences of length 5, two of which are even and one is odd. Write these sequences.

c) How many even sequences and how many odd sequences are there of length 6? And of length 7?

d) There are a total of 377 sequences of length 15, 233 of which are even and 144 are odd. How many sequences are there of length 16? Of these, how many are even? Do not forget to justify your answer.
Solution

a) The sequence is $37 \rightarrow 38 \rightarrow 19 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 6 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 1$.

b) The only sequence of length 3 is $4 \rightarrow 2 \rightarrow 1$. The sequences of length 4 are $3 \rightarrow 4 \rightarrow 2 \rightarrow 1$ and $8 \rightarrow 4 \rightarrow 2 \rightarrow 1$; they are obtained from $4 \rightarrow 2 \rightarrow 1$, the first by adding $4-1=3$ to the left and the second by adding $2 \times 4=8$ to the left. Similarly, the odd sequence $3 \rightarrow 4 \rightarrow 2 \rightarrow 1$ gives rise to the even sequence $6 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 1$; the even sequence $8 \rightarrow 4 \rightarrow 2 \rightarrow 1$ gives rise to the odd sequence $7 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$ and the even sequence $16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$. Thus, we have the three unique sequences of length 5, two of which are even and one is odd. The reasoning can be represented by the following diagram.

![](https://cdn.mathpix.com/cropped/2024_05_01_984603b876c0bc28095bg-25.jpg?height=168&width=626&top_left_y=1852&top_left_x=815)

c) 1st solution: Repeating the scheme from the previous item, we have:

![](https://cdn.mathpix.com/cropped/2024_05_01_984603b876c0bc28095bg-25.jpg?height=477&width=982&top_left_y=2189&top_left_x=640)
and thus we have three even sequences and two odd sequences of length 6, and five even sequences and three odd sequences of length 7.

2nd solution: We observe that the odd sequence of length 5 gives rise to an even sequence of length 6; the two even sequences of length 5 give rise to two even sequences of length 6 and two odd sequences of length 6. Thus, we have two odd sequences of length 6 and $1+2=3$ even sequences of length 6, for a total of $2+3=5$ sequences of length 6. The same argument shows that there are eight sequences of length 7, three of which are odd and five are even.

Observation: Repeating this argument for successive values of the length shows that, starting from length 3, the number of odd sequences is $0,1,1,2,3,5,8, \ldots$, the number of even sequences is $2,3,5,8,13, \ldots$ and the total number of sequences is $3,5,8,13,21, \ldots$ Each term of these sequences of values, starting from the third, is the sum of the two preceding terms; we thus see that these sequences, with the possible omission of initial terms, are the sequence $0,1,1,2,3,5,8,13,21,34,55,89, \ldots$, known as the Fibonacci sequence. We present this result in the table below.

| Length | 5 | 6 | 7 | $\cdots$ | 15 | 16 |
| :---: | :---: | :---: | :---: | :--- | :---: | :---: |
| Odd | 1 | 2 | $1+2=3$ | $\cdots$ | 144 | $89+144=233$ |
| Even | 2 | 3 | $2+3=5$ | $\cdots$ | 233 | $144+233=377$ |
| Total (odd+even) | $1+2=3$ | $2+3=5$ | $3+5=8$ | $\cdots$ | $144+233=377$ | $233+377=610$ |

d) 1st solution: The 144 odd sequences of length 15 give rise to 144 even sequences of length 16; the 233 even sequences of length 15 give rise to 233 even sequences of length 16 and 233 odd sequences of length 16. Thus, we have 233 odd sequences of length 16 and $377=233+144$ even sequences of length 16, for a total of $233+377=610$ sequences.

2nd solution: The part of the Fibonacci sequence that interests us is $1,2,3,5,8, \ldots, 144,233,377,610, \ldots$ The number of odd sequences of length 15 (resp. 16) is the 15th (resp. 16th) term of this sequence, which is 144 (resp. 233); the number of even sequences of length 15 (resp. 16) is the 16th (resp. 17th) term, which is 233 (resp. 377) and the total number is the 17th (resp. 18th) term, which is 377 (resp. 610).