Induction with binomial coefficient

  • #1
Lambda96
186
64
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
  • #2
What about a direct proof? I'm on my phone, so these expressions are hard to post!
 
  • Like
Likes Lambda96
  • #3
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!
 
  • Like
Likes Lambda96
  • #4
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
  • #5
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
  • #6
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##?
 
  • #7
\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
  • #8
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}##
 
  • Like
Likes Lambda96
  • #9
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?
 
  • Like
Likes Lambda96
  • #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)##
 
  • Like
Likes Lambda96
  • #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.
 
  • Like
Likes Lambda96
  • #14
Thanks PeroK for looking over my calculation and thanks for the tip 👍👍, I have now written out my proof in more detail.
 
  • Like
Likes WWGD
  • #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.
 
  • Like
Likes Lambda96
  • #16
I will try the proof via induction again, especially for the exam preparation :book:
 

Similar threads

  • 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
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
Back
Top