How many increasing sequences of natural numbers are there that start with 1, end with 99, and have at least one even number? Prove your answer.

Question

The first thought that came to mind was casework, but there are way too many cases, with the number of even integers ranging from 1 to 45. My second thought was to do complementary counting and count the number of sequences where there were no even integers, so there would be only odd. However, there are still tons of cases to consider. What do I use?

Answer 1

The answer, ignoring the condition, is $2^{97}$; i.e. every subset of $\{2,3,\ldots, 98\}$. We append this subset to $\{1,99\}$, and then order sequentially.

The answer, failing to meet the condition, is $2^{48}$, i.e. every subset of $\{3,5,7,\ldots, 97\}$. We append this subset to $\{1,99\}$, and then order sequentially.

The answer you seek is the difference of the above.