How to apply induction to this formula?

Question

I want to justificate following equation:

$$\sum_{k=0}^n \frac{(-1)^k}{k!(n-k)!}\frac{1}{2k+1} = \frac{2^n}{(2n+1)!!}$$

I calculated the both sides for $n$ from 1 to 10 and it was true. How the mathematical induction can be applied to this equation? Or is there other way to justificate it?

Answer 1

Do you strictly need to use induction? You may simply notice that

$$ \sum_{k=0}^{n}\frac{(-1)^k}{k!(n-k)!}\cdot\frac{1}{2k+1}=\frac{1}{n!}\int_{0}^{1}\sum_{k=0}^{n}\binom{n}{k}(-x^2)^k\,dx=\frac{1}{n!}\int_{0}^{1}(1-x^2)^n\,dx $$ and recall that $\int_{0}^{\pi/2}\left(\sin\theta\right)^{2n+1}\,d\theta = \frac{4^n}{(2n+1)\binom{2n}{n}}$ holds by integration by parts.

Answer 2

The presence of the factor $1/(2k+1)$ in the summation implies that it can actually be obtained by integrating

$$\sum_{k=0}^n\frac{1}{k!(n-k)!}x^{2k},\tag{1}$$

with respect to $x$. Using the Binomial theorem (1) can be easily shown to have the closed form

$$\sum_{k=0}^n\frac{1}{k!(n-k)!}x^{2k}=\frac{(1+x^2)^n}{n!}.$$

Integrating both sides with respect to $x$,

$$\sum_{k=0}^n\frac{1}{k!(n-k)!}\frac{x^{2k+1}}{2k+1}=\frac{x \, _2F_1\left(\frac{1}{2},-n;\frac{3}{2};-x^2\right)}{n!},$$ where $_2F_1$ is the Hypergeometric function. Now let $x=i$ to obtain

$$\sum_{k=0}^n\frac{1}{k!(n-k)!}\frac{(-1)^k}{2k+1}=\frac{\, _2F_1\left(\frac{1}{2},-n;\frac{3}{2};1\right)}{n!}=\frac{\sqrt{\pi }}{2 \Gamma \left(n+\frac{3}{2}\right)}.$$

But $$\Gamma(m+1/2)=\frac{(2m-1)!!}{2^m}\sqrt{\pi},$$ so with $m=n+1$ we obtain the result $$\sum_{k=0}^n\frac{1}{k!(n-k)!}\frac{(-1)^k}{2k+1}=\frac{\sqrt{\pi }}{2 \frac{(2(n+1)-1)!!}{2^{n+1}}\sqrt{\pi}}=\frac{2^n}{(2n+1)!!},$$ as required.

Answer 3

There is a standard technique for this type of sum which has appeared here several times. Introduce

$$f(z) = (-1)^n \frac{1}{2z+1} \prod_{q=0}^n \frac{1}{z-q}.$$

We use the fact that residues sum to zero and we have for the sum over $0\le k\le n$

$$\sum_{k=0}^n \mathrm{Res}_{z=k} f(z) = \sum_{k=0}^n (-1)^n \frac{1}{2k+1} \prod_{q=0}^{k-1} \frac{1}{k-q} \prod_{q=k+1}^{n} \frac{1}{k-q} \\ = \sum_{k=0}^n (-1)^n \frac{1}{2k+1} \frac{1}{k!} \frac{(-1)^{n-k}}{(n-k)!} = \sum_{k=0}^n \frac{1}{k!} \frac{(-1)^k}{(n-k)!} \frac{1}{2k+1}$$

so this is the target sum. The residue at infinity is zero since $\lim_{R\to\infty} 2\pi R/R/R^{n+1} = 0$ so the sum is minus the residue at $z=-1/2.$ We find

$$- \mathrm{Res}_{z=-1/2} f(z) = \frac{(-1)^{n+1}}{2} \prod_{q=0}^n \frac{1}{-1/2-q} = \frac{1}{2} \prod_{q=0}^n \frac{1}{1/2+q} \\ = 2^n \prod_{q=0}^n \frac{1}{2q+1} = \frac{2^n}{(2n+1)!!}.$$

Answer 4

You asked how to do this using induction. To begin with, let's multiply everything by $n!$ so that we can express the terms using binomial coefficients: you want to show $$ \sum_{k=0}^n (-1)^k \binom n k \frac{1}{2k+1} = \frac{(2n) ! ! }{(2n+1)!!}. $$

The difficulty you have is in making the inductive step go through: if you apply the Pascal's triangle identity for $\binom {n+1} k$ then you will end up with terms equivalent to $\binom n k \frac{1}{2k+3}$, and your inductive hypothesis is no help with these.

This suggests strengthening the inductive hypothesis. The right thing to try is proving by induction on $n$ that for any $r$, $$ \sum_{k=0}^n (-1)^k \binom n k \frac{1}{2k+ 2r+1} = (2r-1)!! \frac{(2n)!!}{(2n+2r+1)!!}$$ where you interpret $(2r-1)!!$ as 1 for $r=0$. This is OK for $n=0$ and any $r$ (both sides are $1/(2r+1)$), and you can get the inductive step to go through by using the Pascal's triangle identity $$ \binom {n+1} k = \binom n k + \binom n {k-1}.$$