The sum of difference of two even numbers is even, the sum or difference of two odd numbers is even. The sum or difference of one odd and one even number is even. Fit those into your formula. The crucial point is that in any case one of (n+m)/2 and (n- m+ 1)/2 is an integer and the other is a half integer.