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!
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).