Exercise 3. Consider 7 islands $A_{1}, \ldots, A_{7}$. We are allowed to build bridges, either between an island $A_{i}$ and the next island $A_{i+1}$ (for $i \in\{1,2, \ldots, 6\}$), or between an island $A_{i}$ and the last island $A_{7}$ (for $i \in\{1,2, \ldots, 6\}$). In how many ways can these constructions be carried out with the minimum number of bridges so that one can travel from any island to any other?

Example for 3 islands instead of 7: the three possible constructions using two bridges are

1) a bridge between $A_{1}$ and $A_{2}$, and a bridge between $A_{1}$ and $A_{3}$
2) a bridge between $A_{1}$ and $A_{2}$, and a bridge between $A_{2}$ and $A_{3}$
3) a bridge between $A_{1}$ and $A_{3}$, and a bridge between $A_{2}$ and $A_{3}$.
Solution to Exercise 3 We will say that a configuration is good if it satisfies the conditions of the statement.

Let $a_{n}$ be the number of good configurations with $n$ islands. We have $a_{1}=a_{2}=1$ and $a_{3}=3$.

Starting from a good configuration with $n$ islands such that $A_{n-1}$ and $A_{n}$ are not connected, then $A_{n-1}$ and $A_{n-2}$ are necessarily connected, so if we remove the island $A_{n-1}$ we obtain a good configuration with $n-1$ islands. Conversely, any good configuration with $n-1$ islands comes from one and only one good configuration with $n$ islands where the last two are not connected: it is indeed sufficient to insert an island between the last two and to place a bridge between it and the $n$ - 2-nd one.

We deduce that there are $a_{n-1}$ good configurations with $n$ islands such that $A_{n-1}$ and $A_{n}$ are not connected.

On the other hand, starting from a good configuration with bridges between $A_{n}$ and $A_{n-1}, A_{n-1}$ and $A_{n-2}, \ldots$, $A_{n-k+1}$ and $A_{n-k}(k \geqslant 1)$ but not between $A_{n-k}$ and $A_{n_{k}-1}$, if we remove the islands $A_{n-1}, \ldots, A_{n-k}$ then we obtain a good configuration with $n-k$ islands. We deduce as above that there are $a_{n-1}+a_{n-2}+\cdots+a_{1}$ good configurations with a bridge between $A_{n}$ and $A_{n-1}$.

We see therefore that $a_{n}=2 a_{n-1}+a_{n-2}+\cdots+a_{1}$.

We deduce step by step that $a_{4}=8, a_{5}=21, a_{6}=55$ and $a_{7}=144$.