Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
    
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

3 Answers 3

up vote 0 down vote accepted

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

share|improve this answer
    
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$.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.