I've recently been given this task: there is an array of $n$ binary states, $\{a,b\}$ (for example $n=5$, $aabba$). For given $n$, compute the amount of possible such arrays where there are no 2 congruent $a$'s ($\ldots aa\ldots$ is forbidden). I've solved the problem using a recursive formula too unimportant and complex for me to mention, however, when I printed out the results for $n$ from $1$ to $10$, I've realized that what I'm seeing are the members of the Fibonacci sequence. Can anyone explain/prove why that is?
Thanks, Michael
It backs to your recursive equation. suppose the first character should be $a$ hence, the second character must be $b$, and after that, it would be the new problem with the size of $n-2$. Now, suppose the first problem would be $b$. The part of the problem is a new problem with a size of $n-1$. Hence, if the number of possible combination for $n$ would be $T(n)$ we will have $T(n) = T(n - 1) + T(n - 2)$, and $T(1) = 2$. As you can see it is the equation of the Fibonacci numbers with different start condition.