7
$\begingroup$

Show that $$ \sum_{m=0}^{2k+1}{2^{m}\binom{n}{m}\binom{n-m}{\bigl\lfloor \frac{2k+1-m}{2} \bigr\rfloor}}=\binom{2n+1}{2k+1} $$ I tried expending the sum and using induction, but could not complete the induction step; I tried using Pascal's identity to obtain $$ \binom{n-m}{\bigl\lfloor \frac{2k+3-m}{2} \bigr\rfloor}=\binom{n-m+1}{\bigl\lfloor \frac{2k+3-m}{2} \bigr\rfloor}-\binom{n-m}{\bigl\lfloor \frac{2k+1-m}{2} \bigr\rfloor} $$ but couldn't find other identities to complete the induction step. Searching Gould's Combinatorial Identities brought up nothing, though I could easily had missed something useful there.

I'm looking to complete the induction step, but would also like to find an algebraic or a combinatorial proof. I would like to avoid using trigonometric and root functions, but would like to use complex numbers in cartesian form.

$\endgroup$
6
$\begingroup$

Note: This answer is the result of an analysis of the highly instructive and elegant answer by Marko Riedel. One highlight is the useful representation of $\binom{n}{\left\lfloor \frac{q}{2}\right\rfloor}$ which is the introductory part of this answer.

We use the coefficient of operator $[z^q]$ to denote the coefficient of $z^q$ in a series. This way we can write e.g. \begin{align*} \binom{n}{q}=[z^q](1+z)^n\tag{1} \end{align*} and to ease comparison with Markos answer I will use his notation.

Preliminary:

The following is valid \begin{align*} \binom{n}{\left\lfloor \frac{q}{2}\right\rfloor}=[z^qw^n]\frac{(1+z)(1+w)^n}{1-wz^2}\tag{2} \end{align*}

With $q$ even, $q\rightarrow 2q$ we obtain \begin{align*} [z^{2q}w^n]\frac{(1+z)(1+w)^n}{1-wz^2}&=[w^n](1+w)^n[z^{2q}](1+z)\sum_{j=0}^\infty w^j z^{2j}\tag{3}\\ &=[w^n](1+w)^nw^q\tag{4}\\ &=[w^{n-q}](1+w)^n\tag{5}\\ &=\binom{n}{n-q}=\binom{n}{q} \end{align*} With $q$ odd, $q\rightarrow 2q+1$ we obtain \begin{align*} [z^{2q+1}w^n]\frac{(1+z)(1+w)^n}{1-wz^2}&=[w^n](1+w)^n[z^{2q+1}](1+z)\sum_{j=0}^\infty w^j z^{2j}\\ &=[w^n](1+w)^nw^q\\ &=[w^{n-q}](1+w)^n\\ &=\binom{n}{n-q}=\binom{n}{q} \end{align*}

Comment:

  • Additionally to (1) we use a second variable $z$ which is used as marker to select via $1+z$ even and odd exponent of $w^j$.

  • In (3) we use the geometric series expansion and the linearity of the coefficient of operator.

  • In (4) we select the coefficient of $z^{2q}$ which is $w^q$.

  • In (5) we apply the rule $[z^p]z^qA(z)=[z^{p-q}]A(z)$.

We now apply (2) to OPs formula and obtain \begin{align*} \sum_{k=0}^{2m+1}&\binom{n}{k}2^k\binom{n-k}{\left\lfloor\frac{2m+1-k}{2}\right\rfloor}\\ &=\sum_{k=0}^n\binom{n}{k}2^k[z^{2m+1-k}w^{n-k}]\frac{(1+z)(1+w)^{n-k}}{1-wz^2}\tag{6}\\ &=[z^{2m+1}](1+z)[w^n]\frac{(1+w)^n}{1-wz^2}\sum_{k=0}^n\binom{n}{k}\left(\frac{2wz}{1+w}\right)^k\tag{7}\\ &=[z^{2m+1}](1+z)[w^n]\frac{(1+w)^n}{1-wz^2}\left(1+\frac{2wz}{1+w}\right)^n\\ &=[z^{2m+1}](1+z)[w^n]\frac{(1+w(1+2z))^n}{1-wz^2}\tag{8}\\ &=[z^{2m+1}](1+z)[w^n]\sum_{q=0}^n\binom{n}{q}w^q(1+2z)^q\sum_{j=0}^\infty w^jz^{2j}\\ &=[z^{2m+1}](1+z)\sum_{q=0}^n\binom{n}{q}[w^{n-q}](1+2z)^q\sum_{j=0}^\infty w^jz^{2j}\\ &=[z^{2m+1}](1+z)\sum_{q=0}^n\binom{n}{q}(1+2z)^q\left(z^2\right)^{n-q}\\ &=[z^{2m+1}](1+z)(1+2z+z^2)^n\\ &=[z^{2m+1}](1+z)^{2n+1}\\ &=\binom{2n+1}{2m+1} \end{align*}

and the claim follows.

Comment:

  • In (6) we apply the formula (2) and we change the upper limit of the sum to $n$ without changing anything, since the formula (2) selects the proper range.

  • In (7) we collect all factors with exponent $k$.

  • In (8) observe the factor $(1+w)^n$ cancels nicely.

$\endgroup$
  • 1
    $\begingroup$ Very nice. (+1). This completes the page and the reader should have no trouble following the proof by studying and contrasting the two versions. There is a reason why you are at 34K. $\endgroup$ – Marko Riedel Jan 8 '17 at 18:27
  • $\begingroup$ @MarkoRiedel: Thanks a lot, Marko! :-) $\endgroup$ – Markus Scheuer Jan 8 '17 at 18:32
  • $\begingroup$ Very nice. I love how your suggested notation made things much easier. $\endgroup$ – Hellbound Jan 9 '17 at 10:04
  • $\begingroup$ @BoazK.: You're welcome! Good to see the answer is useful! :-) $\endgroup$ – Markus Scheuer Jan 9 '17 at 10:08
7
$\begingroup$

Here is a combinatorial proof. The right hand side counts the number of ways to choose $2k+1$ elements from a set with $2n+1$ elements. Fix a partition of the latter set into $n+1$ disjoint subsets, namely a singleton and $n$ two-element subsets.

In order to choose such $2k+1$ elements, first we choose the number $m$ of two-element subsets from which we will select exactly one element. Now we choose such subsets, which can be made in $\binom nm$ ways. Finally, from each one of these $m$ subsets we choose exactly one element; this can be made in $2^m$ ways.

It remains to choose the remaining $2k+1-m$ elements among the elements of the singleton and the remaining $n-m$ two-element members of the partition. Because of the previous step, picking an element of one of these two-element subsets forces us to pick the other element as well. Thus, by choosing $\ell$ of these $n-m$ two-element subsets (which can be made in $\binom{n-m}\ell$ ways) we are adding $2\ell$ elements to our $m$ already chosen elements. In other words, at this point we already chose $2\ell+m$ elements.

The important thing to note is that at this point the value of $\ell$ is determined, that is, we cannot "choose" such value. In fact: if $m$ is even, then we necessarily must pick up the element from the singleton subset, and equality $2\ell+m+1=2k+1$ implies $\ell=\frac{2k-m}2=\bigl\lfloor\frac{2k+1-m}2\bigr\rfloor$; if $m$ is odd then we cannot choose the element from the singleton, and in this case $2\ell+m=2k+1$ implies $\ell=\frac{2k+1-m}2=\bigl\lfloor\frac{2k+1-m}2\bigr\rfloor$.

$\endgroup$
  • $\begingroup$ Very nice and easy to follow. $\endgroup$ – Hellbound Jan 9 '17 at 10:06
6
$\begingroup$

Suppose we seek to prove that

$$\sum_{k=0}^{2m+1} {n\choose k} 2^k {n-k\choose \lfloor (2m+1-k)/2 \rfloor} = {2n+1\choose 2m+1}.$$

Observe that from first principles we have that

$${n\choose \lfloor q/2 \rfloor} = {n\choose n-\lfloor q/2 \rfloor} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{q+1}} \\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^n}{w^{n+1}} \left(1+z +wz^2+wz^3 +w^2z^4+w^2z^5+\cdots\right) \; dw \; dz.$$

This simplifies to

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{q+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^n}{w^{n+1}} \left(\frac{1}{1-wz^2}+z\frac{1}{1-wz^2}\right) \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1+z}{z^{q+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^n}{w^{n+1}} \frac{1}{1-wz^2} \; dw \; dz.$$

This correctly enforces the range as the reader is invited to verify and we may extend $k$ beyond $2m+1,$ getting for the sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1+z}{z^{2m+2}} \\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^n}{w^{n+1}} \frac{1}{1-wz^2} \sum_{k\ge 0} {n\choose k} 2^k z^k \frac{w^k}{(1+w)^k} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1+z}{z^{2m+2}} \\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^n}{w^{n+1}} \frac{1}{1-wz^2} \left(1+\frac{2wz}{1+w}\right)^n \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1+z}{z^{2m+2}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w+2wz)^n}{w^{n+1}} \frac{1}{1-wz^2} \; dw \; dz.$$

Extracting the inner coefficient now yields

$$\sum_{q=0}^n {n\choose q} (1+2z)^q z^{2n-2q} = z^{2n} \sum_{q=0}^n {n\choose q} (1+2z)^q z^{-2q} \\= z^{2n} \left(1+\frac{1+2z}{z^2}\right)^n = (1+z)^{2n}.$$

We thus get from the outer coefficient

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1}}{z^{2m+2}} \; dz$$

which is

$$\bbox[5px,border:2px solid #00A000]{ {2n+1\choose 2m+1}}$$

as claimed. I do believe this is an instructive exercise.

$\endgroup$
  • $\begingroup$ Thank you very much. The eureka effect on radical simplification / cancellation was remarkable. $\endgroup$ – Marko Riedel Jan 8 '17 at 11:18
  • 1
    $\begingroup$ @MarkoRiedel: Very nice! Great, Marko! (+1) $\endgroup$ – Markus Scheuer Jan 8 '17 at 11:51
  • $\begingroup$ @MarkoRiedel This wasn't the solution I was looking for but I'm happy and grateful as it motivated the solution of Markus Scheuer and that you seem to have taken some pleasure in solving the problem. $\endgroup$ – Hellbound Jan 9 '17 at 10:02

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.