TheoremProved
Sum of the binomial coefficients
Statement
For every nonnegative integer :
Why is it true?
Setting and both equal to in the binomial theorem turns every term into , so the whole sum collapses to a count of how many terms there are in total.
Proof sketch
Substitute into the binomial theorem : the left side becomes , and the right side becomes , since raised to any power is .
Equating the two sides gives exactly .
This identity also has a direct combinatorial meaning: counts the -element subsets of an -element set , so counts every subset of of any size at all, i.e. the whole power set, which has exactly elements because each of the elements is independently either in or out of a subset.
Topics that use this theorem
Step-by-step proofs
No step-by-step proof yet for this theorem.