# 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$

For any positive integer $$n>1$$ show that this sum $$F(n)=\sum_{k=1}^{+\infty}(2k-1)!!\left(\binom{n-1}{2k-2}-n\binom{n-2}{2k-1}-\binom{n-2}{2k}\right)=1$$

where if $$n>m$$ then $$\binom{m}{n}=0$$

My try: it is clear $$F(2)=1!!(\binom{1}{1}-0-0)=1$$ and $$F(3)=1!!(\binom{2}{0}-3\binom{1}{1}-0)+3!!(\binom{2}{2}-0-0)=1$$ $$F(4)=1!!(\binom{3}{0}-4\binom{2}{1}-\binom{2}{2})+3!!(\binom{3}{2}-0-0)=1$$ and $$F(5)=1,F(6)=1$$,But How to $$F(n)=1,\forall n\in N^{+}$$,I have note $$(n-1)\ge 2k-2,n-2\ge 2k-1,n-2\ge 2k$$,so we have $$k\le [\dfrac{n+1}{2}],k\le [\dfrac{n-1}{2}],k\le [\dfrac{n-2}{2}]$$

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.