Consider the illustrated diagram below:

![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-11.jpg?height=315&width=1174&top_left_y=445&top_left_x=544)

Augusto likes to count paths starting from some point, reaching point $A$ and never passing through the same vertex twice. To do this, he represents a path by the sequence of points that the path visits. For example, the dotted path in the figure below is represented by the sequence $D C B A$.

![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-11.jpg?height=302&width=1168&top_left_y=1034&top_left_x=547)

Augusto calls a path unusual if the sequence representing this path is in reverse alphabetical order. In other words, the path is unusual if it never moves to the left, whether going up or down. For example, the path $D C B A$ is unusual. The path $D B C A$ is not unusual, since the letter $C$ appears before the letter $B$.

a) How many unusual paths exist starting from $D$ and ending at $A$?

b) Show that the number of unusual paths starting from $E$ is the sum of the number of unusual paths starting from $D$ and the number of unusual paths starting from $C$.

c) Augusto calculated the number of unusual paths starting from $K$ and ending at $A$. What is this number?
Solution

a) The unusual paths starting from $D$ and arriving at $A$ are $D C B A$, $D B A$, and $D C A$.

b) An unusual path starting from $E$ must visit one of the points $D$ or $C$ next. In the case where it visits point $D$, its continuation to point $A$ can be any of the unusual paths starting from $D$ and arriving at $A$. In the case where it visits point $C$, its continuation can be any of the unusual paths starting from $C$. Therefore, the total number of unusual paths starting from $E$ is the sum of the number of unusual paths starting from $D$ and the number of unusual paths starting from $E$.

c) To solve this problem, we will rename the points in the diagram. Let $A_{0}=A, A_{1}=B, A_{2}=C$, and so on until $A_{10}=K$.

Let $N(i)$ be the number of unusual paths starting from point $A_{i}$ and arriving at point $A_{0}=A$. Then we have $N(i)=N(i-1)+N(i-2)$ for all $i=2,3, \ldots, 10$. Moreover, there is only one unusual path starting from $A_{1}=B$ and arriving at $A$, and there are two unusual paths starting from $C$ and arriving at $A$, namely $C B A$ and $C A$. Thus, $N(1)=1$ and $N(2)=2$. Then $N(3)=N(1)+N(2)=2+1=3$ (check with the answer to item $a$). Similarly, we have $N(4)=3+2=5$, $N(5)=3+5=8$, and so on.

Following this procedure, we can generate the sequence below, where each number is the sum of its two predecessors:

$$
1,2,3,5,8,13,21,34,55,89,144, \ldots
$$

The $n$-th term of this sequence corresponds to the number of unusual paths starting from $A_{n}$ and arriving at $A$. Thus, the number of unusual paths starting from $K=A_{10}$ and arriving at $A$ is the tenth term of this sequence, which is 89.

Note: The sequence obtained above is the famous Fibonacci sequence.