Skip to page content Home     Posts     CV     Contact     People

Sums with Binomial Coefficients

2017 July 30

Find formulas for each of the following partial sums: $$\sum_{x=0}^n \binom{n}{x}$$ $$\sum_{x=0}^n \binom{n}{x}(-1)^x$$ $$\sum_{x=0}^n \binom{n}{x}x$$ $$\sum_{x=0}^n \binom{n}{x}x^2$$ $$\sum_{x=0}^n \binom{n}{x}x^3$$ $$\sum_{x=0}^n \binom{n}{x}\frac{1}{x+1}$$ $$\sum_{x=0}^n \binom{n}{x}\cos\frac{\pi x}{n}$$ $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}$$

Before we begin, recall these three useful identities regarding the binomial coefficients: $$\binom{n}{x}=\binom{n-1}{x-1}+\binom{n-1}{x}$$ $$\binom{n}{x}=\binom{n+1}{x}-\binom{n}{x-1}$$ $$\binom{n}{x}=\binom{n+1}{x+1}-\binom{n}{x+1}$$ The proofs of these identities are trivial. Also, remember that the formula for the binomail coefficient is $$\binom{n}{x}=\frac{n!}{x!(n-x)!}$$

Furthermore, one more thing that should be mentioned is that the binomial coefficient $$\binom{a}{b}$$ is considered, by convention, to be equal to $0$ whenever $b\lt 0$ or $b\gt a$, and since the binomial coefficient is symmetric, $$\binom{a}{b}=\binom{a}{a-b}$$

To begin this post, I would like to include a proof of the binomial theorem, which can sometimes help with sums involving binomial coefficients. The binomial theorem states that $$(a+b)^n=\sum_{x=0}^n \binom{n}{x}a^xb^{n-x}$$ or, because of the symmetry of the binomial coefficient, $$(a+b)^n=\sum_{x=0}^n \binom{n}{n-x}a^xb^{n-x}$$ and it can be proven rather easily using induction. It is true (trivially) for $n=0$, so we can jump right into the induction step. Suppose that the theorem holds for some $n$ - that is, $$(a+b)^n=\sum_{x=0}^n \binom{n}{n-x}a^xb^{n-x}$$ We want to show that its truth for that $n$ implies its truth for $n+1$. This can be done easily be multiplying both sides of the equation by $a+b$: $$(a+b)^n(a+b)=(a+b)\sum_{x=0}^n \binom{n}{n-x}a^xb^{n-x}$$ Now consider some term in the polynomial expansion of $(a+b)^{n+1}$ containing the term $a^kb^{n-k+1}$. This term can only result from the sum of two such terms after $(a+b)$ is distributed; namely, the sum of the terms $$a\cdot \binom{n}{n-k+1}a^{k-1}b^{n-k+1}$$ and $$b\cdot \binom{n}{n-k}a^{k}b^{n-k}$$ and so the value of their sum is $$a\cdot\binom{n}{n-k+1}a^{k-1}b^{n-k+1}+b\cdot \binom{n}{n-k}a^{k}b^{n-k}$$ $$\binom{n}{n-k+1}a^{k}b^{n-k+1}+\binom{n}{n-k}a^{k}b^{n-k+1}$$ $$\bigg(\binom{n}{n-k+1}+\binom{n}{n-k}\bigg)a^{k}b^{n-k+1}$$ And, by one of our identities, this is equal to $$\binom{n+1}{n-k+1}a^{k}b^{n-k+1}$$ and since each term of the sum follows this form, the entire expansion is equal to $$(a+b)^{n+1}=\sum_{x=0}^{n+1} \binom{n+1}{n-x+1}a^{x}b^{n-x+1}$$ Thus proving the binomial theorem by induction. Now we can begin with our summation problems.

The first two problems are almost trivial if you know the binomial theorem. The first problem $$\sum_{x=0}^n \binom{n}{x}$$ can be rewritten as $$\sum_{x=0}^n \binom{n}{x}1^x1^{n-x}$$ and so, by the binomial theorem, it is equal to $$\sum_{x=0}^n \binom{n}{x}=(1+1)^n$$ $$\sum_{x=0}^n \binom{n}{x}=2^n$$

The second sum $$\sum_{x=0}^n \binom{n}{x}(-1)^x$$ can be rewritten as $$\sum_{x=0}^n \binom{n}{x}(-1)^x1^{n-x}$$ Which, by the binomail theorem, is equal to $$\sum_{x=0}^n \binom{n}{x}(-1)^x=(1-1)^n$$ $$\sum_{x=0}^n \binom{n}{x}(-1)^x=0$$

The first two sums were very easy, but they only get harder from there.

Next up is the sum $$\sum_{x=0}^n \binom{n}{x}x$$ which can be done by expanding the binomial coefficient into its form involving factorials: $$\sum_{x=0}^n \frac{n!}{x!(n-x)!}x$$ and then cancelling the $x$ with the $x$ on the denominator of the binomial coefficient $$\sum_{x=0}^n \frac{n!}{(x-1)!(n-x)!}$$ and then factoring $n$ out of the sum to get $$n\sum_{x=0}^n \frac{(n-1)!}{(x-1)!(n-x)!}$$ $$n\sum_{x=0}^n \binom{n-1}{x-1}$$ And since the last term of this sum will be $$\binom{n-1}{n}=0$$ the sum can be "shortened" to $$n\sum_{x=0}^n \binom{n-1}{x-1}$$ $$n\sum_{x=0}^{n-1} \binom{n-1}{x-1}$$ And since we know that, from our first sum, $$\sum_{x=0}^n \binom{n}{x}=2^n$$ we can convert our sum to $$n2^{n-1}$$ and so $$\sum_{x=0}^n \binom{n}{x}x=n2^{n-1}$$

The next sum is a little bit trickier: $$\sum_{x=0}^n \binom{n}{x}x^2$$ To solve this sum, you need to recognize that $$\sum_{x=0}^n \binom{n}{x}x^2=\sum_{x=0}^n \binom{n}{x}x+\sum_{x=0}^n \binom{n}{x}x(x-1)$$ and so, using the answer to the last problem, $$\sum_{x=0}^n \binom{n}{x}x^2=n2^{n-1}+\sum_{x=0}^n \binom{n}{x}x(x-1)$$ And now we can use the same trick as we did last time and expand the binomial, this time cancelling both $x$ and $x-1$ and extracting $n$ and $n-1$ from the sum: $$\sum_{x=0}^n \binom{n}{x}x^2=n2^{n-1}+\sum_{x=0}^n \frac{n!}{x!(n-x)!}x(x-1)$$ $$\sum_{x=0}^n \binom{n}{x}x^2=n2^{n-1}+\sum_{x=0}^n \frac{n!}{(x-2)!(n-x)!}$$ $$\sum_{x=0}^n \binom{n}{x}x^2=n2^{n-1}+n(n-1)\sum_{x=0}^n \frac{(n-2)!}{(x-2)!(n-x)!}$$ $$\sum_{x=0}^n \binom{n}{x}x^2=n2^{n-1}+n(n-1)\sum_{x=0}^n \binom{n-2}{x-2}$$ and this time we can shorten the sum by the last two terms (because they are both equal to 0) to get $$\sum_{x=0}^n \binom{n}{x}x^2=n2^{n-1}+n(n-1)\sum_{x=0}^{n-2} \binom{n-2}{x-2}$$ $$\sum_{x=0}^n \binom{n}{x}x^2=n2^{n-1}+n(n-1)2^{n-2}$$ Which simplifies to $$\sum_{x=0}^n \binom{n}{x}x^2=n(n+1)2^{n-2}$$

The fifth sum takes this even further. $$\sum_{x=0}^n \binom{n}{x}x^3$$ Again, notice that this sum is equal to $$\sum_{x=0}^n \binom{n}{x}x^3=\sum_{x=0}^n \binom{n}{x}2x-\sum_{x=0}^n \binom{n}{x}3x^2+\sum_{x=0}^n \binom{n}{x}x(x-1)(x-2)$$ $$\sum_{x=0}^n \binom{n}{x}x^3=2\sum_{x=0}^n \binom{n}{x}x-3\sum_{x=0}^n \binom{n}{x}x^2+\sum_{x=0}^n \binom{n}{x}x(x-1)(x-2)$$ Which, by our previous two formulas, is equal to $$\sum_{x=0}^n \binom{n}{x}x^3=2n2^{n-1}-3n(n+1)2^{n-2}+\sum_{x=0}^n \binom{n}{x}x(x-1)(x-2)$$ $$\sum_{x=0}^n \binom{n}{x}x^3=n2^n-3n(n+1)2^{n-2}+\sum_{x=0}^n \binom{n}{x}x(x-1)(x-2)$$ And using the same trick as before, we can expand the binomial coefficient inside of the sum to get $$\sum_{x=0}^n \binom{n}{x}x^3=n2^n-3n(n+1)2^{n-2}+\sum_{x=0}^n \frac{n!}{x!(n-x)!}x(x-1)(x-2)$$ $$\sum_{x=0}^n \binom{n}{x}x^3=n2^n-3n(n+1)2^{n-2}+\sum_{x=0}^n \frac{n!}{(x-3)!(n-x)!}$$ $$\sum_{x=0}^n \binom{n}{x}x^3=n2^n-3n(n+1)2^{n-2}+n(n-1)(n-2)\sum_{x=0}^n \frac{(n-3)!}{(x-3)!(n-x)!}$$ $$\sum_{x=0}^n \binom{n}{x}x^3=n2^n-3n(n+1)2^{n-2}+n(n-1)(n-2)\sum_{x=0}^{n-3} \binom{n-3}{x-3}$$ $$\sum_{x=0}^n \binom{n}{x}x^3=n2^n-3n(n+1)2^{n-2}+n(n-1)(n-2)2^{n-3}$$ And after a bit of algebra, this simplifies to $$\sum_{x=0}^n \binom{n}{x}x^3=n^2(n+3)2^{n-3}$$

Now we have another sum that uses the same method as the previous three, but in reverse: $$\sum_{x=0}^n \binom{n}{x}\frac{1}{x+1}$$ First expand the binomial to get $$\sum_{x=0}^n \binom{n}{x}\frac{1}{x+1}=\sum_{x=0}^n \frac{n!}{x!(n-x)!}\frac{1}{x+1}$$ and then we can proceed to use a very similar trick: $$\sum_{x=0}^n \binom{n}{x}\frac{1}{x+1}=\sum_{x=0}^n \frac{n!}{(x+1)!(n-x)!}$$ $$\sum_{x=0}^n \binom{n}{x}\frac{1}{x+1}=\frac{1}{n+1}\sum_{x=0}^n \frac{(n+1)!}{(x+1)!(n-x)!}$$ $$\sum_{x=0}^n \binom{n}{x}\frac{1}{x+1}=\frac{1}{n+1}\sum_{x=0}^n \binom{n+1}{x+1}$$ $$\sum_{x=0}^n \binom{n}{x}\frac{1}{x+1}=\frac{1}{n+1}\bigg(-1+\sum_{x=0}^{n+1} \binom{n+1}{x+1}\bigg)$$ $$\sum_{x=0}^n \binom{n}{x}\frac{1}{x+1}=\frac{1}{n+1}(2^{n+1}-1)$$ $$\sum_{x=0}^n \binom{n}{x}\frac{1}{x+1}=\frac{2^{n+1}-1}{n+1}$$

Now for the two most difficult sums - I saved the best for last. First we have the sum $$\sum_{x=0}^n \binom{n}{x}\cos\frac{\pi x}{n}$$ I encourage you to try this sum yourself.

It may be tempting to immediately whip out Euler's identity, but first you should stop and think about what the sum represents. When I first attempted this problem, I headed straight into the realm of complex numbers without even thinking about the sum, and when I finally discovered the result, I felt quite foolish.

Consider the case of the sum for which $n$ is odd. Then the sum contains an even number of terms (sine it starts at $x=0$). Consider some term of the sum $$\binom{n}{a}\cos\frac{\pi a}{n}$$ for $x=a$. Now consider the term for $x=n-a$: $$\binom{n}{n-a}\cos\frac{\pi (n-a)}{n}$$ $$=\binom{n}{a}\cos\bigg(\frac{\pi a)}{n}-\pi\bigg)$$ and since $cos(\theta-\pi)=-\cos\theta$, $$=-\binom{n}{a}\cos\frac{\pi a)}{n}$$ It is the opposite of the term for $x=a$! So since, for each $a$ term, the sum also contains a different term for $n-a$, all of the terms cancel out and the sum is equal to zero. The same can be shown for odd $n$ as well, because the middlemost term of the sum would be equal to zero. And so we have $$\sum_{x=0}^n \binom{n}{x}\cos\frac{\pi x}{n}=0$$

The last sum, however, is non-trivial and has a rather beautiful solution, given that the binomial coefficients do not seem like they would create a sum that condenses to any closed form when multiplied by a trigonometric function. And this time, we will lead our attempt with Euler's identity. $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}$$ Using Euler's identity, this sum can be converted into $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}=\Im\bigg[\sum_{x=0}^n \binom{n}{x}e^\frac{\pi ix}{n}\bigg]$$ and using our old friend the binomial theorem, we have $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}=\Im\big[(e^\frac{\pi i}{n}+1)^n\big]$$ $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}=\Im\big[(\cos\frac{\pi}{n}+i\sin\frac{\pi}{n}+1)^n\big]$$ Here's where the tricky part occurs. To continue from here, you need to use the fact that $$\frac{\pi}{n}=2\cdot\frac{\pi}{2n}$$ and then use the double-angle formulas, like this: $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}=\Im\big[(\cos2\cdot\frac{\pi}{2n}+i\sin2\cdot\frac{\pi}{2n}+1)^n\big]$$ $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}=\Im\big[(\cos^2\frac{\pi}{2n}-\sin^2\frac{\pi}{2n}+2i\sin\frac{\pi}{2n}\cos\frac{\pi}{2n}+1)^n\big]$$ $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}=\Im\big[(\cos^2\frac{\pi}{2n}+2i\sin\frac{\pi}{2n}\cos\frac{\pi}{2n}+1-\sin^2\frac{\pi}{2n})^n\big]$$ Then use the fact that $1-\sin^2\theta=\cos^2\theta$ to change this to $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}=\Im\big[(\cos^2\frac{\pi}{2n}+2i\sin\frac{\pi}{2n}\cos\frac{\pi}{2n}+\cos^2\frac{\pi}{2n})^n\big]$$ $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}=\Im\big[(2\cos^2\frac{\pi}{2n}+2i\sin\frac{\pi}{2n}\cos\frac{\pi}{2n})^n\big]$$ Then factor out $2\cos\frac{\pi}{2n}$ from the whole thing to get $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}=\Im\big[2^n\cos^n\frac{\pi}{2n}(\cos\frac{\pi}{2n}+i\sin\frac{\pi}{2n})^n\big]$$ $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}=2^n\cos^n\frac{\pi}{2n}\Im\big[(\cos\frac{\pi}{2n}+i\sin\frac{\pi}{2n})^n\big]$$ Perhaps the hardest part of all in evaluating this sum is knowing the identity known as "De Moivre's Formula": $$(\cos\theta+i\sin\theta)^n=\cos n\theta+i\sin n\theta$$ I will omit the proof, as it can be done easily using induction. Using it, we have $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}=2^n\cos^n\frac{\pi}{2n}\Im\big[\cos n\cdot\frac{\pi}{2n}+i\sin n\cdot\frac{\pi}{2n}\big]$$ $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}=2^n\cos^n\frac{\pi}{2n}\Im\big[\cos\frac{\pi}{2}+i\sin\frac{\pi}{2}\big]$$ $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}=2^n\cos^n\frac{\pi}{2n}\Im[0+i]$$ $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}=2^n\cos^n\frac{\pi}{2n}\Im[i]$$ $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}=2^n\cos^n\frac{\pi}{2n}\cdot 1$$ $$\sum_{x=0}^n \binom{n}{x}\sin\frac{\pi x}{n}=2^n\cos^n\frac{\pi}{2n}$$ And there you have it - a very beautiful formula linking the binomial coefficients to the trigonometric functions.

That's all the summation I'm going to do in this post!