Induction with binomial coefficient

  • Thread starter Thread starter Lambda96
  • Start date Start date
  • Tags Tags
    Induction Proof
Lambda96
Messages
233
Reaction score
77
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.
 
Physics news on Phys.org
What about a direct proof? I'm on my phone, so these expressions are hard to post!
 
Start with this

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!
 
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:
  • Informative
  • Like
Likes Lambda96 and berkeman
Integrate from 0 to 1 the identity

##(1-x)^n=\sum\limits_{k=0}^{n} \binom{n}{k} (-1)^kx^k##
 
  • Like
Likes 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.
 
  • Like
Likes 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 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?
 
  • #10
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)##
 
  • #11
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)}$$
 
  • Like
Likes Lambda96 and fresh_42
  • #12
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?
 
  • #13
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.
 
  • #14
Thanks PeroK for looking over my calculation and thanks for the tip 👍👍, I have now written out my proof in more detail.
 
  • #15
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.
 
  • #16
I will try the proof via induction again, especially for the exam preparation :book:
 
Back
Top