# Binomial theorem

The following formula holds: $$(a+b)^n = \displaystyle\sum_{k=0}^n {n \choose k} a^k b^{n-k},$$ where ${n \choose k}$ denotes the binomial coefficient
We will proceed using induction. If $n=0$ then $$(a+b)^0 = 1 = {0 \choose 0} a^0 b^0 = \displaystyle\sum_{k=0}^0 {0 \choose k} a^k b^{0-k}.$$ We assume that $$(a+b)^n = \displaystyle\sum_{k=0}^n {n \choose k} a^k b^{n-k}.$$ Now compute using binomial coefficient (n choose 0) equals 1 and binomial coefficient ((n+1) choose k) equals (n choose k) + (n choose (k-1)), we see $$\begin{array}{ll} (a+b)^{n+1} &= (a+b) (a+b)^n \\ &=(a+b) \displaystyle\sum_{k=0}^n {n \choose k} a^k b^{n-k} \\ &= \left[ \displaystyle\sum_{k=0}^n {n \choose k} a^{k+1} b^{n-k} \right] + \left[ \displaystyle\sum_{k=0}^n {n \choose k} a^k b^{n-k+1} \right] \\ &= \left[ \displaystyle{n \choose n} a^{n+1} + \displaystyle\sum_{k=0}^{n-1} {n \choose k} a^{k+1} b^{n-k} \right] + \left[ \displaystyle{n \choose 0} b^{n+1}+ \displaystyle\sum_{k=1}^{n} {n \choose k} a^k b^{n-k+1} \right] \\ &=a^{n+1} + b^{n+1} + \left[ \displaystyle\sum_{k=0}^{n-1} {n \choose k} a^{k+1} b^{n-k} \right] + \left[ \displaystyle\sum_{k=1}^{n} {n \choose k} a^k b^{n-k+1} \right] \\ &=a^{n+1} + b^{n+1} + \left[ \displaystyle\sum_{k=1}^{n} {n \choose {k-1}} a^{k} b^{n-k+1} \right] + \left[ \displaystyle\sum_{k=1}^{n} {n \choose k} a^k b^{n-k+1} \right] \\ &= \displaystyle{{n+1} \choose 0} a^{n+1} + \displaystyle{{n+1} \choose {n+1}} b^{n+1} + \displaystyle\sum_{k=1}^n \left[ {n \choose {k-1}} + {n \choose k} \right] a^k b^{n-k+1} \\ &=\displaystyle{{n+1} \choose 0} a^{n+1} + \displaystyle{{n+1} \choose {n+1}} b^{n+1} + \displaystyle\sum_{k=1}^n {{n+1} \choose k} a^k b^{n-k+1} \\ &= \displaystyle\sum_{k=0}^{n+1} {{n+1} \choose k} a^k b^{n-k+1}, \end{array}$$ proving the claim.