The binomial theorem

We prove it by induction on $n$. Base case $n=1$: $(a+b)^1=a+b=\binom{1}{0}a+\binom{1}{1}b$, which matches the formula since $\binom{1}{0}=\binom{1}{1}=1$.

Inductive step: assume the formula holds for some $n$, so $(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k$. Multiply both sides by $(a+b)$: $(a+b)^{n+1}=\sum_{k=0}^n\binom{n}{k}a^{n+1-k}b^k+\sum_{k=0}^n\binom{n}{k}a^{n-k}b^{k+1}$.

Reindexing the second sum with $j=k+1$ and collecting the coefficient of $a^{n+1-j}b^j$ from both sums gives $\binom{n}{j}+\binom{n}{j-1}$ for each $j$ from $0$ to $n+1$ (with the convention $\binom{n}{-1}=\binom{n}{n+1}=0$).

By Pascal's rule $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$, this sum equals $\binom{n+1}{j}$, so $(a+b)^{n+1}=\sum_{j=0}^{n+1}\binom{n+1}{j}a^{n+1-j}b^j$, completing the induction.