Combinatorics, Binomial Theorem and Differentiation

Binomial Theorem and Differentiation

What is the sum of k×(n:k), i.e. k times (n choose k), as k runs from 0 to n? These types of questions don't come up very often, but when they do, there's a trick.

Remember that (1+x)ⁿ is the sum of (n:k) × x^k, by the binomial theorem. Differentiate this with respect to x, then substitute x = 1. The right side is the sum of k×(n:k), which is exactly what we want. The left side becomes n×2^n-1.

If we are interested in the sum of k²×(n:k), take the second derivative and replace x with 1. This isn't quite right, because you get the sum of k×(k-1)×(n:k), but you can always ad n×2^n-1 back in. This cancels the -k in k×(k-1). The answer is (n²+n)×2^n-2. Note that similar formulas can be derived for the sum of k³×(n:k), and so on.