Counting odd and even compositions of integers

Question

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?

Could you please help me to understand this?

Thanks in advance!

@jspecter of course, I never thought it could be so simple, thanks! — muffel, Jun 25 '11 at 23:56

score 3 · Accepted Answer · answered Jun 25 '11 at 23:31

3

Hint: If $x$ is even then $x-1$ is odd, and vice versa.

answered Jun 25 '11 at 23:31

Yuval Filmus

57,157

Filmus thanks! No idea why I missed that... – muffel Jun 25 '11 at 23:56

Counting odd and even compositions of integers

1 Answers1