Binomial Theorem and Differentiation

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)n is the sum of (n:k) × xk, 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×2n-1.

If we are interested in the sum of k2×(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×2n-1 back in.  This cancels the -k in k×(k-1).  The answer is (n2+n)×2n-2.  Note that similar formulas can be derived for the sum of k3×(n:k), and so on.