2020 IMO SL #C1

 Let $n$ be a positive integer. Find the number of permutations $a_1$, $a_2$, $\dots a_n$ of the sequence $1$, $2$, $\dots$ , $n$ satisfying $$a_1 \le 2a_2\le 3a_3 \le \dots \le na_n.$$

Let $f(n)$ be the number of such permutations for some $n$, and let $F_n$ denote the $n$th Fibonacci number. 

The answer is $\boxed{F_{n+1}}$. 

Note that $f(1)=1$ and $f(2)=2$. 

We now show that $f(n)=f(n-1)+f(n-2)$ for all $n \geq 3$. 

First of all, we claim that $a_n=n-1, n$. 

If $a_n=n$, then the last inequality is satisfied, so permuting the remaining numbers is equivalent to the problem for $n-1$, so there are $f(n-1)$ ways. 

If $a_{n-1}=n$, then the only possible value of $a_n$ satisfying the last inequality is $n-1$. Then the rest of the problem is equivalent to permuting the first $n-2$ numbers, for which there are $a_{n-2}$ ways.

We claim that there are no other permutations. For the sake of contradiction, assume otherwise. Suppose $a_i=n$ where $i < n-1$. Note that for all numbers less than $i$, they must appear before $a_i$ because it is impossible that when an integer at most $n$ is multiplied to it, it will equal or exceed $ni$. This fills up all slots of the permutation before $a_i$. Then, $i$ must be equal to $a_n$, or else the inequality fails. This means that all terms from $ia_i$ to $na_n$ must be equal to $ni$. But $n-1$ does not divide $ni$ as $ni=i(n-1)+i$ and $i<n-1$, so we have a contradiction.

Therefore, we know that $f(n)=f(n-1)+f(n-2)$. Now, based on our first values $f(1)=1,f(2)=2$ and this recursion, we know that the answer is $F_{n+1}$, as desired. $\square$