# Fibonacci series in 0-Even-Odd-Even-Odd-N series up to N

Another question from the test for the Normale of Pisa:

Consider the series $S_n$ of integer numbers repeteandly even - odd - even - odd that start with 0 and finish with n, so with n = 3 we get 2 series: $$\left\{{0,1,2,3}\right\} ; \left\{{0,3}\right\}$$

So $S_3 = 2$.

Show that $S_n$ are the Fibonacci numbers.

$S_1 = 1 \\ S_2 = 1 \\ S_3 = 2 \\ S_4 = 3$

-
Hint: Show by induction that $S_n = S_{n-1}+S_{n-2},\,n\geq 3$. –  Lord Soth Apr 1 '13 at 20:11
Thanks, I think I got that. –  Siscia Apr 1 '13 at 20:29

HINT:

$$\begin{array}{ccc} n=4&&n=5&&n=6\\ \hline \begin{array}{ll} -\\ -\\ -\\ -\\ -\\ 0,1,2,3,\color{green}{4}\\ 0,1,\color{green}{4}\\ 0,3,\color{green}{4}\\ \end{array}&& \begin{array}{ll} 0,1,2,3,4,5\\ 0,1,2,5\\ 0,1,4,5\\ 0,3,4,5\\ 0,5\\ -\\ -\\ -\\ \end{array}&& \begin{array}{ll} 0,1,2,3,4,5,\color{red}{6}\\ 0,1,2,5,\color{red}{6}\\ 0,1,4,5,\color{red}{6}\\ 0,3,4,5,\color{red}{6}\\ 0,5,\color{red}{6}\\ 0,1,2,3,\color{green}{6}\\ 0,1,\color{green}{6}\\ 0,3,\color{green}{6} \end{array} \end{array}$$

Added: vonbrand’s answer gives one way to express this idea in general form. Here’s another. Let $\mathscr{S}(n)$ be the set of sequences for $n$, so that $S_n=|\mathscr{S}(n)|$. Now split $\mathscr{S}(n)$ into two subsets: $\mathscr{S}_0(n)$ is the set of sequences that include $n-1$, and $\mathscr{S}_1(n)$ is that set of sequences that don’t include $n-1$. Every sequence in $\mathscr{S}_0(n)$ is obtained by appending $n$ to a sequence in $\mathscr{S}(n-1)$, and you can append $n$ to any sequence in $\mathscr{S}(n-1)$ to get a sequence in $\mathscr{S}_0(n)$. Thus, $|\mathscr{S}_0(n)|=S_{n-1}$.

Now look at a sequence in $\mathscr{S}_1(n)$; it ends in $n$, and it does not include $n-1$. It can’t include $n-2$, either, because $n-2$ and $n$ would be adjacent terms with the same parity. Let $m$ be the last term before the $n$. Then $m<n-2$, and $m$ has the opposite parity to $n-2$ and $n$. This means that if we replace $n$ by $n-2$, the resulting sequence is in $\mathscr{S}(n-2)$. Conversely, if you start with a sequence in $\mathscr{S}(n-2)$ and replace the $n-2$ by $n$, you get a sequence in $\mathscr{S}_1(n)$. Thus, $|\mathscr{S}_1(n)|=S_{n-2}$.

-
So n of 7 would be just the whole n of 6 plus a 7 in the end of the series plus the n of 5 series with the 5 replace by a 7... I got that... thanks a lot... I need a way to express it in a math way... I really lack on rigor. –  Siscia Apr 1 '13 at 20:31
@Siscia: See my addition and, for a slightly different way of looking at it, vonbrand’s answer. –  Brian M. Scott Apr 1 '13 at 20:56
I did thanks it is really clear, I got the idea... It is funny how a problem who looked so "unsolvable" for me now looks pretty trivial... –  Siscia Apr 1 '13 at 21:00
@Siscia: You’re welcome. You’ll find that combinatorial problems are often like that: if you can just find the right way to look at them, they’re much easier. –  Brian M. Scott Apr 1 '13 at 21:06

By your comment to BrianM.Scott's answer, you could say: To get the sequences for $n + 2$, you take all sequences for $n + 1$ and add $n + 2$ at the end, or all the sequences for $n$ and replace the $n$ at the end by $n + 2$. As the two types of sequences are disjoint (the $n$ sequences are prefixes of the $n + 1$ sequences, by the way they are constructed), we have $S_{n + 2} = S_{n + 1} + S_n$.

-

To prof the thesis I need to prof that $S_n = S_{n-1} + S_{n-2}$

Starting with any $n$ either even or odd, the next series $S_{n+1}$ would be at least as big as $S_n$ since I can simply add $n+1$ at the end of every $S_n$ series.

Then the $S_{n+1}$ will also integrate the $S_{n-1}$ series because I can simply replace the last number of every $S_{n-1}$ series with $n+1$.

Finally is easy to show that the series from $S_{n-1}$ cannot be the same of the series from the $S_n$, this because one series finish always with an odd number while the other with an even one.

-