I would not concentrate on numbers of combinations, when talking about even and odd numbers we know that

odd + odd = even
odd + even = odd
even + odd = odd
even + even = even

This can be generalised to

sum( any number of even numbers ) = even
sum( any number of even numbers plus an even number of odd numbers) = even
sum( any number of even numbers plus an odd number of odd numbers) = odd

So the question can be restated as I pick m integers from (1, 2, 3, ..., n ) what is the probability that I have an odd number of odd numbers.

Without telling you the answer consider the cases m=1, m=2 (shown above), m=3, this will give you a clue to the answer without proving it however from these results generalise a solution of m+1 to prove the answer.