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.
Answer
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.
No comments:
Post a Comment