Induction with binomial coefficient

[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.

 

[PeroK]

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

 

[PeroK]

Start with this

##\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!

 

[fresh_42]

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.

 

[martinbn]

Integrate from 0 to 1 the identity

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

 

[Lambda96]

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

 

[fresh_42]

\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.

 

[PeroK]

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

 

[fresh_42]

@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?

 

[WWGD]

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

 

[PeroK]

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]

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?

 

[PeroK]

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.

 

[PeroK]

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