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