count of the strictly increasing sub sequences of ${{1,2, ...,n-1,n}}$ of size k where each member of the subsequence serves the condition $x_i +i $ is even and $ 1<= i<= k$ and $k<=n$
There is another question similar to this one which I have seen is still answerless , I tried reducing the problem to a recursive problem where we consider the number of similar sequence of size $k-1$ as $B_{k-1}$ and the complete count as $B_{k}$ then we can divide the problem into two parts: for odd $k$ s we have $B_{k}$=$B_{k-1}$.SOMETHING which I am not sure of ...
another approach would be to consider the general problem for different $i$ s : for odd $i$ s we have to choose an odd $a_i$ and for an even $i$ an even $a_i$ then we can just choose the two subsets of odd and even numbers in the sequence and the big problem would be to re arrange the picked numbers in a way that the strictly increasing property is kept .
any help would be appericiated
Let $S_n$ be the solution, we find a recursion for $S_n$ (We allow for the empty subsequence).
If you don't include number $1$ then you can't include $2$ either and so there are $S_{n-2}$ ways to do it.
If you do include number $1$ then you can look at the subsequence without the first element in it, and the condition is it has to start even and alternate, only now we have one less option, but we start even, so it is analogous to the problem but for $n-1$, so there are $S_{n-1}$ ways to do it.
It follows that $S_n = S_{n-1} + S_{n-2}$.
$S_1=1$ as only the empty subsequence works.
$S_2 = 2$ as the empty one and $(1)$ work.
$S_3 = 3$ as the empty one and $(1)$ and $(1,2)$ work.
$s_4 = 5$ as the empty one and $(1,2,3)$ and $(1,2)$ and $(1)$ and $(3)$ work.
Therefore $s_n = F_{n-1}$ Where $F$ is the fibonacci sequence.