# Proving combinatoric identity using the inclusion-exclusion principle

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!

• Sorry to be vague, but it will probably be something like: $k$ is the number of violations of the red-neighbors rule. – 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.