3
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ I'm very curious - could you explain what you counted on the LHS for the simple case? $\endgroup$ – Nitin Oct 28 '16 at 4:28
  • $\begingroup$ 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? $\endgroup$ – Q the Platypus Oct 28 '16 at 5:34
  • 1
    $\begingroup$ @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$. $\endgroup$ – Robert Z Oct 28 '16 at 5:47
2
$\begingroup$

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

$\endgroup$

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.