In other words, we are asked to find the number of increasing sequences of elements in $[n]$ which are alternatively even and odd. Now, I just guessed the answer, and this makes things a lot easier . For each $n$, let $o_n$ be the number of such sequences which begin with an odd number, and $e_n$ the number of sequences which begin with an even number (so the value we're trying to find is $a(n)=o_n+e_n$). We have $o_n=(o_{n-1}+1)+(o_{n-3}+1)+\ldots$ (we define $o_0=0$, and the sum goes on for as long as the indices are non-negative), because if your sequence begins with $1$, then you can either leave it like this, or extend it in $o_{n-1}$ ways, if it begins with $3$, you can leave it like this or extend it in $o_{n-3}$ ways, and so on. It is also obvious that $e_n=o_{n-1}$. We can observe now that $x_n=F_{n+2}-1$ has the same initial values as $o_n$ and satisfies the same recurrence, where $F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2},\ \forall n\ge 2$ is the Fibonacci sequence. This means that we have $o_n=F_{n+2}-1$, and we thus have $a(n)=o_n+e_n=F_{n+3}-2$.