How to prove a specific sequence is Fibonacci's with no prior knowledge nor trial and error? 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.
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$
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.