How prove this sum $\sum_{k=1}^{+\infty}(2k-1)!!\left(\binom{n-1}{2k-2}-n\binom{n-2}{2k-1}-\binom{n-2}{2k}\right)=1$

Solution 1:

We show for $n\geq 2$ the validity of $F(n)=1$ with the help of generating functions. It is somewhat more convenient to consider $F(n+2)$ instead of $F(n)$ and we claim:

The following is valid for $n\geq 0$: \begin{align*} \color{blue}{\sum_{k\geq 1}\left(\binom{n+1}{2k-2}-(n+2)\binom{n}{2k-1}-\binom{n}{2k}\right)(2k-1)!!=1}\tag{1} \end{align*}

The sum (1) is finite since $\binom{p}{q}=0$ for $p,q$ non-negative integers with $q>p$. We use the coefficient of operator $[z^q]$ to denote the coefficient of $z^q$ in a series. We consider each of the parts at the left-hand side of (1) separately and put them together at the end.

First part: We obtain \begin{align*} \color{blue}{\sum_{k=1}^{\left\lfloor\frac{n+3}{2}\right\rfloor}}&\color{blue}{\binom{n+1}{2k-2}(2k-1)!!}\\ &=\sum_{k=1}^{\left\lfloor\frac{n+3}{2}\right\rfloor}\frac{(n+1)!}{(2k-2)!(n+3-2k)!}\,\frac{(2k )!}{(2k)!!}\\ &=\sum_{k=1}^{\left\lfloor\frac{n+3}{2}\right\rfloor}\frac{(n+1)!}{(n+3-2k)!}\,\frac{2k(2k-1)}{2^kk!}\\ &=\sum_{k=1}^{\left\lfloor\frac{n+3}{2}\right\rfloor}\frac{(n+1)!}{(n+3-2k)!}\,\frac{2k-1}{2^{k-1}(k-1)!}\\ &=\sum_{k=0}^{\left\lfloor\frac{n+1}{2}\right\rfloor}\frac{(n+1)!}{(n+1-2k)!}\,\frac{2k+1}{2^kk!}\tag{2}\\ &=\sum_{k=1}^{\left\lfloor\frac{n+1}{2}\right\rfloor}\frac{(n+1)!}{(n+1-2k)!}\,\frac{1}{2^{k-1}(k-1)!} +\sum_{k=0}^{\left\lfloor\frac{n+1}{2}\right\rfloor}\frac{(n+1)!}{(n+1-2k)!}\,\frac{1}{2^{k}k!}\tag{3}\\ &=\sum_{k=0}^{\left\lfloor\frac{n+1}{2}\right\rfloor}\frac{(n+1)!}{(n-1-2k)!}\,\frac{1}{2^{k}k!} +\sum_{k=0}^{\left\lfloor\frac{n+1}{2}\right\rfloor}\frac{(n+1)!}{(n+1-2k)!}\,\frac{1}{2^{k}k!}\tag{4}\\ &\,\,\color{blue}{=(n+1)!\left([z^{n-1}]+[z^{n+1}]\right)\exp\left(z+\frac{z^2}{2}\right)}\tag{5} \end{align*}

Comment:

• In (2) we shift the index $k$ by one and start with $k=0$.

• In (3) we split the sums according to $2k+1$ and cancel at the left-hand sum. Since the term with $k=0$ is zero at the left-hand sum, we start with $k=1$.

• In (4) we shift the index $k$ of the left-hand sum by one.

• In (5) we observe we have the coefficients $[z^{n-1}]$ and $[z^{n+1}]$ of $\exp\left(z\right)\exp\left(\frac{z^2}{2}\right)=\exp\left(z+\frac{z^2}{2}\right)$. The derivation for it is similar to that of the third part and is shown there.

Second part: We obtain \begin{align*} \color{blue}{\sum_{k=1}^{\left\lfloor\frac{n+1}{2}\right\rfloor}}&\color{blue}{\binom{n}{2k-1}(2k-1)!!}\\ &=\sum_{k=1}^{\left\lfloor\frac{n+1}{2}\right\rfloor}\frac{n!}{(2k-1)!(n+1-2k)!}\,\frac{(2k )!}{(2k)!!}\\ &=\sum_{k=1}^{\left\lfloor\frac{n+1}{2}\right\rfloor}\frac{n!}{(n+1-2k)!}\,\frac{2k}{2^kk!}\\ &=\sum_{k=1}^{\left\lfloor\frac{n+1}{2}\right\rfloor}\frac{n!}{(n+1-2k)!}\,\frac{1}{2^{k-1}(k-1)!}\\ &=\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}\frac{n!}{(n-1-2k)!}\,\frac{1}{2^kk!}\\ &\,\,\color{blue}{=n![z^{n-1}]\exp\left(z+\frac{z^2}{2}\right)}\tag{6} \end{align*}

Comment:

• In (6) we observe we have a coefficient of $[z^{n-1}]$ of $\exp\left(z+\frac{z^2}{2}\right)$. The derivation for it is similar to that of the third part and is shown there.

Third part: The third part is very similar to the parts before, but it has additionally a nice twist which provides us with the constant $1$. We obtain \begin{align*} \color{blue}{\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}}&\color{blue}{\binom{n}{2k}(2k-1)!!}\\ &=\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\frac{n!}{(2k)!(n-2k)!}\,\frac{(2k )!}{(2k)!!}\\ &=\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\frac{n!}{(n-2k)!}\,\frac{1}{2^kk!}\tag{7}\\ &\,\,\color{blue}{=n![z^{n}]\left(\exp\left(z+\frac{z^2}{2}\right)-\exp(z)\right)}\tag{8} \end{align*}

Comment:

• In (8) we have the funny intermediate result: \begin{align*} n![z^{n}]\exp(z)=n![z^n]\sum_{j=0}^\infty \frac{z^j}{j!}\color{blue}{=1} \end{align*}

and the further procedure is clear: We expect that the sum of the coefficients of $\exp\left(z+\frac{z^2}{2}\right)$ cancel away leaving the constant $n![z^{n}]\exp(z)=1$. But at first we have to show the validity of (8).

Derivation of (8): We get \begin{align*} \color{blue}{\exp}&\color{blue}{\left(z+\frac{z^2}{2}\right)-\exp(z)}\\ &=\exp(z)\left(\exp\left(\frac{z^2}{2}\right)-1\right)\\ &=\left(\sum_{j=0}^\infty\frac{z^j}{j!}\right)\left(\sum_{k=1}^\infty\frac{z^{2k}}{2^kk!}\right)\\ &=\sum_{n=0}^\infty\left(\sum_{{j+2k=n}\atop{j\geq 0, k\geq 1}}\frac{1}{j!}\,\frac{1}{2^kk!}\right)z^n\\ &\,\,\color{blue}{=\sum_{n=0}^\infty\left(\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\frac{n!}{(n-2k)!}\,\frac{1}{2^kk!}\right)\frac{z^n}{n!}} \end{align*} and the claim (8) follows.

Now it's (nearly) time to harvest. Let's collect the representation of the parts (5),(6) and (8) we have so far:

Final step: We obtain from (1), (5), (6) and (8) \begin{align*} \color{blue}{\sum_{k\geq 1}}&\color{blue}{\left(\binom{n+1}{2k-2}-(n+2)\binom{n}{2k-1}-\binom{n}{2k}\right)(2k-1)!!}\\ &=(n+1)!\left([z^{n-1}]+[z^{n+1}]\right)\exp\left(z+\frac{z^2}{2}\right)\\ &\qquad-(n+2)n![z^{n-1}]\exp\left(z+\frac{z^2}{2}\right)\\ &\qquad-n![z^{n}]\left(\exp\left(z+\frac{z^2}{2}\right)-\exp(z)\right)\\ &=\left((n+1)![z^{n+1}]-n![z^n]-n![z^{n-1}]\right)\exp\left(z+\frac{z^2}{2}\right)\color{blue}{+1}\tag{9} \end{align*}

We want to show the coefficients in (9) cancel away. In order to do so, we consider \begin{align*} A(z)&=\sum_{n=0}^\infty a_nz^n=\exp\left(z+\frac{z^2}{2}\right)\\ \\ \frac{d}{dz}A(z)&=\sum_{n=1}^\infty na_nz^{n-1}\tag{10}\\ \frac{d}{dz}\exp\left(z+\frac{z^2}{2}\right)&=(1+z)\exp\left(z+\frac{z^2}{2}\right)\tag{11}\\ \end{align*}

Coefficient comparison of (10) and (11) gives: \begin{align*} (n+1)a_{n+1}&=\color{blue}{(n+1)[z^{n+1}]A(z)}\\ &=[z^n](1+z)\exp\left(z+\frac{z^2}{2}\right)\\ &\,\,\color{blue}{=\left([z^n]+[z^{n-1}]\right)A(z)} \end{align*} which shows that in (9) \begin{align*} \left((n+1)![z^{n+1}]-n![z^n]-n![z^{n-1}]\right)\exp\left(z+\frac{z^2}{2}\right)=0 \end{align*} and the claim (1) follows.