I recently came across this question:
Starting from 10, you start counting down to reach 1: a) If the previous 2 numbers are the same, then the following number must be 2 less than them. Eg.(..6,6,4..) but not (..6,6,5..)
b) If the previous 2 numbers are different, then the following number must be the same or 1 less than than the previous number. Eg. (..6,5,4..) or (..6,5,5..) but not (..6,5,3..)
Using these rules, how many ways are there to count down from 10?
I solved it by going through all the possible combinations for 1 number, 2 numbers.. 6 numbers and found the fibonacci sequence in the amount of ways you can count down from those numbers. Eg. (1=1,2=1,3=2...6=8). By this logic I figured that the amount of times you can count down from 10 is the 10th fibonacci number, i.e. 55.
What I'm asking is whether or not my answer of 55 is correct, and if there is a mathematical way to determine the correct answer?
Let $a_n$ be the number of ways to count down from $n$ to $1$ when the previous two numbers are different. As mentioned, there are two options.
The next element can be the same, i.e. can be $n$. In this case, the subsequent number must be $n-2$. You must then count down from $n-2$ to $1$, which can be done in $a_{n-2}$ ways.
The next element can be one less than $n$. In this case, the sequence can be completed in $a_{n-1}$ ways.
This shows that $a_n=a_{n-1}+a_{n-2}$, so $a_n$ obeys the Fibonacci recurrence. As long as $a_1$ and $a_2$ are consecutive Fibonacci numbers, then $a_n$ will be Fibonacci for all $n$.