I need to prove the identity ${\displaystyle \sum_{k=0}^{n}(-1)^{k}{2n-k \choose k}2^{2n-2k}=2n+1} $ using the inclusion-exclusion principle. It was hinted to think about the number of ways to color the numbers ${1,..,2n}$ in the colors red and blue such that if $i$ is colored red so is $i-1$. Well, it is clearly why the number of ways to do it is $2n+1$, but I don't manage to show why it also equal to the left side of the equation.

Anyone can give me a hint about the sets I should define in order to use the inclusion-exclusion principle? Thanks!

  • $\begingroup$ Sorry to be vague, but it will probably be something like: $k$ is the number of violations of the red-neighbors rule. $\endgroup$ – Greg Martin May 22 '13 at 17:14

There are $2^{2n}$ colourings in total, $2^{2n-2}{2n-1\choose 1}$ ways to pick a pair of adjacent numbers and colour the first blue and the second red and the rest any colour, $2^{2n-4}{2n-2\choose 2}$ ways to pick two pairs of numbers and have both with the first color blue and the second colour red and the rest any colour, and so on.

  • $\begingroup$ Thanks a lot! :) $\endgroup$ – John Smith May 22 '13 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.