# Prove combinatorial identity using coloring

I encountered a problem which is stated as follows: Color the integers $1$ to $2n$ red or blue in such a way that if $i$ is red then $i-1$ is red too. Use this to prove that

$\sum^n_{k=0}(-1)^k\binom{2n-k}{k} 2^{2n-2k} = 2n+1$

and verify it using generating functions. Use $m+1$ colors to derive the identity

$\sum_{k\geq 0 }(-1)^k\binom{n-k}{k} m^k(m+1)^{n-2k} = \frac{m^{n+1}-1}{m-1}$, for $m\geq 2$

I think I got the first part, for the second part the RHS can be converted to $\sum_{k=0}^nm^k$, but I don't know how to go from there.

Any help would be appreciated!

• I'm very curious - could you explain what you counted on the LHS for the simple case? – Nitin Oct 28 '16 at 4:28
• I'm a little bit confused by the wording of this question. If i-1 is red for all i's that are red then isn't all of 1 to 2n red or blue? Because if i is red, then i-1 has to be red as well but if i-1 is red then doesn't i-2 also have to be red? – Q the Platypus Oct 28 '16 at 5:34
• @Q the Platypus In the first case if $2n=4$ then the colorings which satisfy the condition are $2n+1=5$: $BBBB$, $RBBB$, $RRBB$, $RRRB$, $RRRR$. – Robert Z Oct 28 '16 at 5:47

## 1 Answer

In the second part we have to color the integers $1,2,\dots, n$ with $(m+1)$ colors (one is red) in such a way that if $i>1$ is red then $i−1$ is red too.

In the LHS of $$\sum_{k\geq 0 }(-1)^k\binom{n-k}{k} m^k(m+1)^{n-2k}=\sum_{k=0}^nm^k$$ we are using the Inclusion-exclusion Principle. The number $$\binom{n-k}{k} m^k(m+1)^{n-2k}$$ counts the number of ways the we can choose $k$ couples of adjacent points ($\binom{n-k}{k}$ ways) where the point on the left is not-red ($m^k$ ways) and the one on the right is red (so there are at least $k$ red points which do not satisfy the given condition). The remaining $(n-2k)$ points are colored with one of the $(m+1)$ colors ($(m+1)^{n-2k}$ ways).

In the RHS, $m^k$ is the number of ways to have the first $n-k$ points colored with red and the remaining $k$ points colored with one of the $m$ not-red colors (and the condition is satisfied).