How to prove a specific sequence is Fibonacci's with no prior knowledge nor trial and error?

Question

Let $n$ be a positive integer and let $s_n$ be the number of increasing sequences of integers, alternatingly even and odd, starting with $0$ and ending with $n$. E.g. for $n=3$ we only have the two sequences $$ 0,1,2,3 \ \ \text{and} \ \ 0,3.$$ hence $s_3=2$. Prove that the $s_n$ are the Fibonacci numbers.

Here's the deal. We already know that the sequence is Fibonacci's, so it suffices to show that $s_n$ satisfies the recursive definition of $F_n$. And it is in fact straightforward to put the sequences for $n=k,k+1$ into one-to-one correspondence with those for $n=k+2$. So what I'm looking for is an approach able to find that $s_n=F_n$, without knowing it beforehand or guessing.

Answer 1

So the number of sequences $s_{n+1}$ ending in $n+1$ is obtained by adding $n+1$ to sequences ending in $n$ or ...

you can't add $n+1$ to a sequence ending in $n-1$ because they have the same parity. But you can substitute $n+1$ for $n-1$ at the end of a sequence because they have the same parity.

Every sequence ending in $n+1$ can be obtained in this way, because either the penultimate element is $n$ or it is less than $n-1$ (parity again).

Hence $s_{n+1}=s_n+s_{n-1}$ and it suffices to show that $s_1=s_2=1$

Answer 2

If you did not know beforehand that the result is Fibonacci then start by trying to find a relation for $s_n$ in terms of its previous terms.

Answer 3

Suppose $A_n$ is the set of sequences corresponding to $s_n$. Pick a sequence from $A_n$, appending $n+1,n+2$ to it we get a sequence in $A_{n+2}$. Pick a sequence in $A_{n+1}$, appending $n+2$ to it gets us a sequence in $A_{n+2}$. So we have $$\#(A_{n+2})\ge\#(A_n)+\#(A_{n+1})\implies s_{n+2}\ge s_{n}+s_{n+1}$$ where $\#$ denotes the number of elements in a set or its cardinality. Now pick a sequence in $A_{n+2}$. If the penultimate term is $n+1$, remove the last term to get a sequence in $A_{n+1}$. If the penultimate term is not $n+1$, remove the last two terms. If the reduced sequence has $n$ as its last term we get a sequence in $A_n$ and if not simply replace the last term with $n$ and we still get a member of $A_n$. So we have $$ \#(A_{n+2})\le\#(A_n)+\#(A_{n+1})\implies s_{n+2}\le s_n+s_{n+1}\\ \therefore s_{n+2}=s_{n}+s_{n+1} $$ Now check that $s_0=1,s_1=1$ and you're good to go.