11
$\begingroup$

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}]$

$\endgroup$
1

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

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.