Proof for $\sum_{k=0}^{n}\frac{(-1)^k}{k+1}\binom{n}{k}=\frac{1}{n+1}$ using induction.

Question

I'm trying to prove $\sum_{k=0}^{n}\frac{(-1)^k}{k+1}\binom{n}{k}=\frac{1}{n+1}$ by induction, but I got stuck along the way and can't figure the next step out, or where I went wrong (I've read some posts about it so I know that this isn't the best/fastest way). This is my progress so far: $$$$base case: $n=1$ $$\sum_{k=0}^1\frac{(-1)^k}{k+1}\binom{1}{k}=1-\frac{1}{2}=\frac{1}{2}=\frac{1}{1+1}.$$ induction step: $n+1$ $$\sum_{k=0}^{n+1}\frac{(-1)^k}{k+1}\binom{n+1}{k}=\sum_{k=0}^{n}\frac{(-1)^k}{k+1}\binom{n+1}{k}+\frac{(-1)^{n+1}}{n+2}\binom{n+1}{n+1}\\=\sum_{k=0}^{n}\frac{(-1)^k}{k+1}\left(\binom{n}{k}+\binom{n}{k-1}\right)+\frac{(-1)^{n+1}}{n+2}\\=\frac{1}{n+1}+\sum_{k=0}^{n}\frac{(-1)^k}{k+1}\binom{n}{k-1}+\frac{(-1)^{n+1}}{n+2}\\=\frac{1}{n+1}+\sum_{k=0}^{n-1}\frac{(-1)^{k+1}}{k+2}\binom{n}{k}+\frac{(-1)^{n+1}}{n+2}\\=\frac{1}{n+1}+\sum_{k=0}^{n}\frac{(-1)^{k+1}}{k+2}\binom{n}{k}$$ The last step is where I'm stuck. I'm not quite sure if I just can't see the next step I have to take, or if I made a mistake along the way. Help would be appreciated, thanks in advance.

Answer 1

We have the induction hypothesis: \begin{align*} \color{blue}{\sum_{k=0}^{n}\frac{(-1)^k}{k+1}\binom{n}{k}=\frac{1}{n+1}}\tag{1} \end{align*}

The induction step is \begin{align*} \color{blue}{\sum_{k=0}^{n+1}}&\color{blue}{\frac{(-1)^k}{k+1}\binom{n+1}{k}}\tag{2}\\ &=1+\sum_{k=1}^{n}\frac{(-1)^k}{k+1}\left(\binom{n}{k}+\binom{n}{k-1}\right)+\frac{(-1)^{n+1}}{n+2}\tag{3}\\ &=\sum_{k=0}^{n}\frac{(-1)^k}{k+1}\binom{n}{k}+\sum_{k=1}^{n+1}\frac{(-1)^k}{k+1}\binom{n}{k-1}\tag{4}\\ &=\frac{1}{n+1}+\frac{1}{n+1}\sum_{k=1}^{n+1}\frac{(-1)^k}{k+1}\binom{n+1}{k}(k+1-1)\tag{5}\\ &=\left(\frac{1}{n+1}+\frac{1}{n+1}\sum_{k=1}^{n+1}(-1)^k\binom{n+1}{k}\right) -\frac{1}{n+1}\sum_{k=1}^{n+1}\frac{(-1)^k}{k+1}\binom{n+1}{k}\\ &=\frac{1}{n+1}(1-1)^{n+1}-\frac{1}{n+1}\sum_{k=0}^{n+1}\frac{(-1)^k}{k+1}\binom{n+1}{k}+\frac{1}{n+1}\tag{6}\\ &\,\,\color{blue}{=-\frac{1}{n+1}\sum_{k=0}^{n+1}\frac{(-1)^k}{k+1}\binom{n+1}{k}+\frac{1}{n+1}}\tag{7} \end{align*}

From (2) and (7) we obtain \begin{align*} \left(1+\frac{1}{n+1}\right)\sum_{k=0}^{n+1}\frac{(-1)^k}{k+1}\binom{n+1}{k}&=\frac{1}{n+1}\\ \color{blue}{\sum_{k=0}^{n+1}\frac{(-1)^k}{k+1}\binom{n+1}{k}}&\color{blue}{=\frac{1}{n+2}} \end{align*} and the claim follows.

Comment:

• In (3) we separate the first and last term of the sum and apply $\binom{p}{q}=\binom{p-1}{q}+\binom{p-1}{q-1}$.

• In (4) we split the sum and merge the left-most and right-most terms.

• In (5) we apply the induction hypothesis (1) to the left-hand sum. We also apply the binomial identity $\binom{p+1}{q+1}=\frac{p+1}{q+1}\binom{p}{q}$.

• In (6) we use the binomial theorem. We also start the sum with index $k=0$ and add $\frac{1}{n+1}$ as compensation.