Saturday, February 25, 2017

discrete mathematics - Induction on a sum



The left hand side has terms involving
\binom{n}{m}= \dfrac{n!}{(n-m)!m!}



1+\dfrac{1}{2}\binom{n}{1} +\frac{1}{3}\binom{n}{2}+...........+\frac{1}{n+1}\binom{n}{n} = \dfrac{2^{n+1}-1}{n+1}




I've done induction and proved P(0) holds and also P(1),P(2) holds (Just in case)



Now I've found P(K+1) so the sum on the left is going to equal \dfrac{2^{n+1}-1}{n+1} + \dfrac{1}{n+2}



and the right hand side is going to equal \dfrac{2^{n+2}-1}{n+2}



My problem is coming with the algebra though. I can't get those sides to equal. I can't get rid of the n+1 in the denominator.



Anyone have any ideas for me? They'd be much appreciated!




P.S. Someone gave me a hint and said that you can use the binomial theorem to solve this.


Answer



Recall that
(1+x)^n = \sum_{k=0}^n \dbinom{n}k x^k
Integrating this from 0 to 1, gives us
\left. \dfrac{(1+x)^{n+1}}{n+1} \right \vert_{0}^1 = \sum_{k=0}^n \dbinom{n}k \left. \dfrac{x^{k+1}}{k+1} \right \vert_0^1
Hence, we get what you want.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f \colon A \rightarrow B and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...