Saudi Arabian Mathematical Competitions, 2015

Let $A_{n}$ be the set of such sequences with the last term is $n$ instead of $15$, and $a_{n}=|A_{n}|$. We will show that $(a_{n})$ is in fact the Fibonacci sequence and deduce that $a_{15}=610$.

We can check easily that $a_{1}=a_{2}=1$. For $n \geq 1$, we consider the second-last term of each sequence in $A_{n+2}$. We have two cases.

Case 1. The second-last term is $n+1$. Then we can leave out the last term to get an element of $A_{n+1}$. Conversely, for each element of $A_{n+1}$, we can add $n+2$ to the end to have an element of $A_{n+2}$. Hence, in this case, we have $a_{n+1}$ sequences.

Case 2. The second-last term is at most $n$. But $n$ and $n+2$ have the same parity, so the second-last term is at most $n-1$. When we substitute the last term $n+2$ with $n$, we have an element of $A_{n}$. Conversely, if we replace $n$ in an element of $A_{n}$ by $n+2$, we have an element of $A_{n+2}$. Hence, in this case, we have $a_{n}$ sequences.

This proves that $a_{n+2}=a_{n+1}+a_{n}$, and therefore $(a_{n})$ is the Fibonacci sequence.