# Counting odd and even compositions of integers

A composition of the number $n$ with $k$ summands is the representation $$n = a_1 + \cdots + a_k$$ with integers $a_i \geq 1, 1 \leq i \leq k$. The order of the summands is important.

Prove: There are as many compositions of n with k even summands as compositions of n-k with k odd summands exist.

Hi!

I don't have any idea how to prove that as I don't know how to handle this "odd" and "even" stuff. Bijection? Induction?

A bijection will do (subtract one from each $a_i$). –  jspecter Jun 25 '11 at 23:32
Hint: If $x$ is even then $x-1$ is odd, and vice versa.