Let \( n \) be a positive integer. Find the number of permutations \( a_{1}, a_{2}, \ldots, a_{n} \) of the sequence \( 1, 2, \ldots, n \) satisfying 
\[ a_{1} \leqslant 2 a_{2} \leqslant 3 a_{3} \leqslant \ldots \leqslant n a_{n} \]
(United Kingdom) Answer: The number of such permutations is \( F_{n+1} \), where \( F_{k} \) is the \( k^{\text{th}} \) Fibonacci number: \( F_{1} = F_{2} = 1, F_{n+1} = F_{n} + F_{n-1} \).
Denote by $P_{n}$ the number of permutations that satisfy (*). It is easy to see that $P_{1}=1$ and $P_{2}=2$. Lemma 1. Let $n \geqslant 3$. If a permutation $a_{1}, \ldots, a_{n}$ satisfies (*) then either $a_{n}=n$, or $a_{n-1}=n$ and $a_{n}=n-1$. Proof. Let $k$ be the index for which $a_{k}=n$. If $k=n$ then we are done. If $k=n-1$ then, by (*), we have $n(n-1)=(n-1) a_{n-1} \leqslant n a_{n}$, so $a_{n} \geqslant n-1$. Since $a_{n} \neq a_{n-1}=n$, the only choice for $a_{n}$ is $a_{n}=n-1$.  Now suppose that $k \leqslant n-2$. For every $k < i \leq n$, we have $a_{i} > k$, so $a_{n} \geqslant k+1$. Now the $n-k+1$ numbers $a_{k}, a_{k+1}, \ldots, a_{n}$ are all greater than $k$; but there are only $n-k$ such values; this is not possible.  If $a_{n}=n$ then $a_{1}, a_{2}, \ldots, a_{n-1}$ must be a permutation of the numbers $1, \ldots, n-1$ satisfying $a_{1} \leqslant 2 a_{2} \leqslant \ldots \leqslant(n-1) a_{n-1}$; there are $P_{n-1}$ such permutations. The last inequality in (*), $(n-1) a_{n-1} \leqslant n a_{n}=n^{2}$, holds true automatically.  If $\left(a_{n-1}, a_{n}\right)=(n, n-1)$, then $a_{1}, \ldots, a_{n-2}$ must be a permutation of $1, \ldots, n-2$ satisfying $a_{1} \leqslant \ldots \leqslant(n-2) a_{n-2}$; there are $P_{n-2}$ such permutations. The last two inequalities in (*) hold true automatically by $(n-2) a_{n-2} \leqslant(n-2)^{2}<n(n-1)=(n-1) a_{n-1}=n a_{n}$.  Hence, the sequence $\left(P_{1}, P_{2}, \ldots\right)$ satisfies the recurrence relation $P_{n}=P_{n-1}+P_{n-2}$ for $n \geqslant 3$. The first two elements are $P_{1}=F_{2}$ and $P_{2}=F_{3}$, so by a trivial induction we have $P_{n}=F_{n+1}$.