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$
 A: 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$.
A: 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}$.
A: 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.
