Increasing Sum of Binomial Coefficients

Theorem

Let $n \in \Z$ be an integer.

Then:

$\displaystyle \sum_{j=0}^n j \binom n j = n 2^{n-1}$

where $\displaystyle \binom n k$ denotes a binomial coefficient.

That is:

$\displaystyle 1 \binom n 1 + 2 \binom n 2 + 3 \binom n 3 + \cdots + n \binom n n = n 2^{n-1}$

Proof

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \sum_{j=0}^n j \binom n j\)	\(=\)	\(\displaystyle \sum_{j=1}^n j \binom n j\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	as $\displaystyle 0 \binom n 0 = 0$
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sum_{j=1}^n n \binom {n-1} {j-1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Factors of Binomial Coefficients
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle n \sum_{j=0}^{n-1} \binom {n-1} j\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Permutation of Indices
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle n 2^{n-1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Sum of Binomial Coefficients for Given n

$\blacksquare$

Sources

• Murray R. Spiegel: Mathematical Handbook of Formulas and Tables (1968): $3.14$