# Induction with binomial coefficient

• Lambda96
Lambda96
Homework Statement
##\sum\limits_{k=0}^{n} \frac{(-1)^k}{k+1} \binom{n}{k}=\frac{1}{n+1}##
Relevant Equations
none
Hi,

I'm having problems with the proof for the induction of the following problem: ##\sum\limits_{k=0}^{n} \frac{(-1)^k}{k+1} \binom{n}{k}=\frac{1}{n+1}## with ##n \in \mathbb{N}##

I proceeded as follows:

$$\sum\limits_{k=0}^{n+1} \frac{(-1)^k}{k+1} \binom{n+1}{k}=\frac{1}{n+2}$$
$$\sum\limits_{k=0}^{n+1} \frac{(-1)^k}{k+1} \biggl(\binom{n}{k} +\binom{n}{k-1} )=\frac{1}{n+2}$$
$$\sum\limits_{k=0}^{n} \frac{(-1)^k}{k+1} \binom{n}{k} +\sum\limits_{k=0}^{n+1} \frac{(-1)^k}{k+1}\binom{n}{k-1} =\frac{1}{n+2}$$
$$\frac{1}{n+1} + \sum\limits_{k=0}^{n+1} \frac{(-1)^k}{k+1} \binom{n}{k-1}=\frac{1}{n+2}$$

Unfortunately, I can't get any further now because I don't know how to solve the term ##\sum\limits_{k=0}^{n+1} \frac{(-1)^k}{k+1} \binom{n}{k-1}## and how to simplify it further. According to mathematica, the term would be ##-\frac{1}{n^2+3n+2}## and if I calculate ##\frac{1}{n+1}-\frac{1}{n^2+3n+2}=\frac{1}{n+2}##, I get the required result.

What about a direct proof? I'm on my phone, so these expressions are hard to post!

Lambda96

Lambda96 said:
##\sum\limits_{k=0}^{n} \frac{(-1)^k}{k+1} \binom{n}{k}##
Take out a factor of ##\frac1 {n+1}## and then the resulting sum must be ##1##, which I think is easy to prove.

You can then use this to get the other identity above that you needed for induction!

Lambda96
A general note. You shouldn't use the equality sign if you still have to prove equality! So your proofwriting should be
\begin{align*}
\sum_{k=0}^{n+1}\dfrac{(-1)^k}{k+1}\binom{n+1}{k} &=1+\dfrac{(-1)^{n+1}}{n+2}+\sum_{k=1}^{n}\dfrac{(-1)^k}{k+1}\binom{n+1}{k}\\
&=1+\dfrac{(-1)^{n+1}}{n+2}+\sum_{k=1}^{n}\dfrac{(-1)^k}{k+1}\left[\binom{n}{k}+\binom{n}{k-1}\right]\\
&=1+\sum_{k=1}^{n}\dfrac{(-1)^k}{k+1}\binom{n}{k}-\dfrac{(-1)^{n}}{n+2}+\sum_{k=1}^{n}\dfrac{(-1)^k}{k+1}\binom{n}{k-1}\\
&=\sum_{k=0}^{n}\dfrac{(-1)^k}{k+1}\binom{n}{k}-\dfrac{(-1)^{n}}{n+2}-\sum_{j=0}^{n-1}\dfrac{(-1)^j}{j+2}\binom{n}{j}\\
&=\dfrac{1}{n+1}-\dfrac{(-1)^{n}}{n+2}-\sum_{j=0}^{n-1}\dfrac{(-1)^j}{j+2}\binom{n}{j}\\
&=\dfrac{1}{n+1}-\sum_{j=0}^{n}\dfrac{(-1)^j}{j+2}\binom{n}{j}\\
&=\ldots\\
&\phantom{=}\vdots\\
&=\dfrac{1}{n+2}
\end{align*}
where ##1/(n+2)## only occurs when you actually arrived there.

I only wrote with a grain of salt what you already had, so it'll be no help. I got stuck in the same position.
A direct proof as @PeroK has suggested is definitely worth a try.

Last edited:
Lambda96 and berkeman
Integrate from 0 to 1 the identity

##(1-x)^n=\sum\limits_{k=0}^{n} \binom{n}{k} (-1)^kx^k##

Lambda96 and PeroK
Thank you PeroK, fresh_42 and martinbn for your help.

I wanted to use the tip from PeroK, with the factoring out of ##\frac{1}{n+1}## and got the following:

$$\sum\limits_{k=0}^{n}\frac{(-1)^k}{k+1} \binom{n}{k}=\sum\limits_{k=0}^{n}\frac{(-1)^k}{k+1} \frac{k+1}{n+1} \binom{n+1}{k+1}$$
$$\sum\limits_{k=0}^{n}\frac{(-1)^k}{k+1} \binom{n}{k} = \frac{1}{n+1} \sum\limits_{k=0}^{n}(-1)^k \binom{n+1}{k+1}$$

Unfortunately, I now have problems showing that the term ##\sum\limits_{k=0}^{n}(-1)^k \binom{n+1}{k+1}## is equal to 1.

@martinbn Did you mean the following ##\int_{0}^{1} (1-x)^n \,dx##?

\begin{align*}
0&=(1-1)^{n+1}=\sum_{j=0}^{n+1} \binom{n+1}{j}1^{n+1-j}(-1)^j\\
&=1+\sum_{j=1}^{n+1} \binom{n+1}{j}1^{n+1-j}(-1)^j=1+\sum_{k=0}^n \binom{n+1}{k+1}(-1)^{k+1}
\end{align*}

That is what I wanted to show you in my first reply.
• Changing the index variable by substitutions of the kind ##k \leftrightarrows j\pm 1## is often necessary when dealing with such sums.
• The boundaries at the bottom and at the top of sums often require a specific treatment if we substitute the index since they are trivially right or wrong, or carry negative indices after the substitution which we do not want.

Lambda96 and PeroK
Lambda96 said:
Unfortunately, I now have problems showing that the term ##\sum\limits_{k=0}^{n}(-1)^k \binom{n+1}{k+1}## is equal to 1.
i thought you'd see that is closely related to ##(1 -1)^{n+1}##

Lambda96
Lambda96 said:
@martinbn Did you mean the following ##\int_{0}^{1} (1-x)^n \,dx##?
Let's put it the other way around: what do you get if you integrate the equation?

Lambda96
Interesting. Maybe it would help to find the general form for ##\frac{1}{k}-\frac{1}{k+1}##, for context.

Edit ## n^2+3n+2=(n+1)(n+2)##

Lambda96
Lambda96 said:
Homework Statement: ##\sum\limits_{k=0}^{n} \frac{(-1)^k}{k+1} \binom{n}{k}=\frac{1}{n+1}##
Here's a generalisation that you may want to try to prove. For ##m \ge 1##:
$$\sum\limits_{k=0}^{n}\frac{(-1)^k}{k+m}\binom n k = \frac{(m -1)!}{(n+1)\dots(n+m)}$$Your identity is the case for ##m =1## and the next one is:
$$\sum\limits_{k=0}^{n}\frac{(-1)^k}{k+2}\binom n k = \frac 1 {(n+1)(n+2)}$$

Lambda96 and fresh_42
Thank you PeroK, fresh_42 and WWGD for your help. I have now tried the direct proof with the identity that martinbn suggested.I have now proceeded as follows:

$$=\sum\limits_{k=0}^{n}\frac{(-1)^k}{k+1} \binom{n}{k} x^{k+1}$$Then I formed the derivative with respect to x

$$=\sum\limits_{k=0}^{n} (-1)^k \binom{n}{k}x^k$$
$$=\sum\limits_{k=0}^{n} (-x)^k \binom{n}{k}$$
$$=\sum\limits_{k=0}^{n} (-x)^k 1^{n-k} \binom{n}{k}$$

Then I can use the binomial theorem, so the sum is ##(1-x)^n##

I then get the following equation ##(1-x)^n=\sum\limits_{k=0}^{n} (-x)^k 1^{n-k} \binom{n}{k}## which I integrate from 0 to 1:

$$\int\limits_{0}^{1} (1-x)^n \ dx=\int\limits_{0}^{1} \sum\limits_{k=0}^{n} (-x)^k 1^{n-k} \binom{n}{k} \ dx$$
$$\frac{1}{n+1}=\sum\limits_{k=0}^{n} \frac{(-1)^k}{k+1} 1^{n-k} \binom{n}{k}$$
$$\frac{1}{n+1}=\sum\limits_{k=0}^{n} \frac{(-1)^k}{k+1} \binom{n}{k}$$

Would that work as a proof?

Lambda96 said:
Thank you PeroK, fresh_42 and WWGD for your help. I have now tried the direct proof with the identity that martinbn suggested.I have now proceeded as follows:

$$=\sum\limits_{k=0}^{n}\frac{(-1)^k}{k+1} \binom{n}{k} x^{k+1}$$Then I formed the derivative with respect to x

$$=\sum\limits_{k=0}^{n} (-1)^k \binom{n}{k}x^k$$
$$=\sum\limits_{k=0}^{n} (-x)^k \binom{n}{k}$$
$$=\sum\limits_{k=0}^{n} (-x)^k 1^{n-k} \binom{n}{k}$$

Then I can use the binomial theorem, so the sum is ##(1-x)^n##

I then get the following equation ##(1-x)^n=\sum\limits_{k=0}^{n} (-x)^k 1^{n-k} \binom{n}{k}## which I integrate from 0 to 1:

$$\int\limits_{0}^{1} (1-x)^n \ dx=\int\limits_{0}^{1} \sum\limits_{k=0}^{n} (-x)^k 1^{n-k} \binom{n}{k} \ dx$$
$$\frac{1}{n+1}=\sum\limits_{k=0}^{n} \frac{(-1)^k}{k+1} 1^{n-k} \binom{n}{k}$$
$$\frac{1}{n+1}=\sum\limits_{k=0}^{n} \frac{(-1)^k}{k+1} \binom{n}{k}$$

Would that work as a proof?
It's not wrong, but I'd say it's a bit ragged. You labour some points, like keeping the term ##1^{n-k}##, but skip any details of the integration entirely. The idea is simply$$(1 - x)^n = \sum\limits_{k=0}^{n} 1^{n-k}(-x)^k \binom{n}{k} = \sum\limits_{k=0}^{n} (-1)^k x^k \binom{n}{k}$$Hence:$$\int_0^1 (1 - x)^n dx = \int_0^1 \sum\limits_{k=0}^{n} (-1)^k x^k \binom{n}{k} dx = \sum\limits_{k=0}^{n} (-1)^k \binom{n}{k} \int_0^1 x^k dx$$Then do the integration.

Lambda96
Thanks PeroK for looking over my calculation and thanks for the tip , I have now written out my proof in more detail.

WWGD
Lambda96 said:
Thanks PeroK for looking over my calculation and thanks for the tip , I have now written out my proof in more detail.
By the way, the induction you tried unsuccessfully in your OP works quite well to prove the general result! Once you have proved the case for ##m = 1##, you can do an induction on ##m##. See post #11.

Lambda96
I will try the proof via induction again, especially for the exam preparation

• Calculus and Beyond Homework Help
Replies
6
Views
599
• Calculus and Beyond Homework Help
Replies
1
Views
386
• Calculus and Beyond Homework Help
Replies
5
Views
653
• Calculus and Beyond Homework Help
Replies
14
Views
2K
• Calculus and Beyond Homework Help
Replies
1
Views
496
• Calculus and Beyond Homework Help
Replies
7
Views
1K
• Calculus and Beyond Homework Help
Replies
12
Views
977
• Calculus and Beyond Homework Help
Replies
3
Views
618
• Calculus and Beyond Homework Help
Replies
5
Views
641
• Calculus and Beyond Homework Help
Replies
1
Views
516