Sum Identity

ABSTRACT

The Sum Identity, also known as the Sum of Binomial Coefficients, states that the sum of all entries in the $n$-th row of Pascal’s Triangle is exactly $2^n$. This identity provides the fundamental link between binomial expansion and the total number of subsets in a power set.

---

The Identity

$$\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{0}\right)+\left(\genfrac{}{}{0ex}{}{n}{1}\right)+\left(\genfrac{}{}{0ex}{}{n}{2}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{n}{n}\right)=2^n$$

---

1. Algebraic Proof

Using the Binomial Theorem, we can expand $(x+y{)}^n$:

$$(x+y{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^{n-k}{y}^k$$

By substituting $x=1$ and $y=1$:

$$\begin{array}{rl}(1+1{)}^n& =\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)(1{)}^{n-k}(1{)}^k\\ 2^n& =\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)\cdot 1\cdot 1\\ 2^n& =\left(\genfrac{}{}{0ex}{}{n}{0}\right)+\left(\genfrac{}{}{0ex}{}{n}{1}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{n}{n}\right)\end{array}$$

---

2. Combinatorial Proof

We can prove this by showing that both sides of the equation count the same set of objects: the total number of binary strings of length $n$.

• RHS ($2^n$): For a binary string of length $n$, each of the $n$ positions has 2 choices (0 or 1). By the Product Rule, there are $2\times 2\times \cdots \times 2=2^n$ total strings.
• LHS ($\sum \left(\genfrac{}{}{0ex}{}{n}{k}\right)$): We can partition the set of all binary strings by their weight (the number of 1s they contain).
  • Strings with zero 1s: $\left(\genfrac{}{}{0ex}{}{n}{0}\right)$
  • Strings with one 1: $\left(\genfrac{}{}{0ex}{}{n}{1}\right)$
  • Strings with $k$ 1s: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$

INFO

By the Sum Rule, the total number of strings is the sum of these disjoint cases from $k=0$ to $n$.

---

3. Connection to Power Sets

This identity also counts the total number of subsets of a set $S$ where $|S|=n$:

• $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ represents the number of ways to choose a subset of size $k$.
• Summing from $k=0$ (the empty set) to $k=n$ (the set itself) gives every possible subset.
• Therefore, the size of the Power Set is always $2^n$.

---

Example ($n=4$)

$$\begin{array}{rl}{2}^4& =\left(\genfrac{}{}{0ex}{}{4}{0}\right)+\left(\genfrac{}{}{0ex}{}{4}{1}\right)+\left(\genfrac{}{}{0ex}{}{4}{2}\right)+\left(\genfrac{}{}{0ex}{}{4}{3}\right)+\left(\genfrac{}{}{0ex}{}{4}{4}\right)\\ 16& =1+4+6+4+1\\ 16& =16\end{array}$$

• 1 empty set $\varnothing$
• 4 subsets of size 1
• 6 subsets of size 2
• 4 subsets of size 3
• 1 subset of size 4 (the set itself)