# Proof: By Induction

(related to Theorem: Binomial Theorem)

Let $$x,y\in R$$ and let $$(R,+,\cdot)$$ be a ring. The proof is by complete induction by the natural number $$n$$.

### $$(1)$$ Base case $$n=0$$

Because $$(x+y)^0=1$$ and $$\sum_{k=0}^0{0\choose k}x^{n-k}y^k={0\choose 0}x^{0}y^0=1$$, it is true that $(x+y)^0=\sum_{k=0}^0{0\choose k}x^{n-k}y^k.$

### $$(2)$$ Induction step $$n\to n+1$$

$\begin{array}{rcl} (x+y)^{n+1}&=&(x+y)^n(x+y)\\ &=&\left(\sum_{k=0}^n{n\choose k}x^{n-k}y^k\right)(x+y)\\ &=&\sum_{k=0}^n{n\choose k}x^{n+1-k}y^k + \sum_{k=0}^n{n\choose k}x^{n-k}y^{k+1}\quad\quad\text{(distributivity and associativity laws in }R\text{)}\\ &=&\left(x^{n+1}+\sum_{k=1}^n{n\choose k}x^{n+1-k}y^k\right) + \left(\sum_{k=0}^{n-1}{n\choose k}x^{n-k}y^{k+1}+y^{n+1}\right)\quad\quad\text{(separation of terms from both sums)}\\ &=&\left(x^{n+1}+\sum_{k=1}^n{n\choose k}x^{n+1-k}y^k\right) + \left(\sum_{k=1}^{n}{n\choose {k-1}}x^{n-(k-1)}y^{k}+y^{n+1}\right)\quad\quad\text{(change of index in second sum)}\\ &=&x^{n+1}+\sum_{k=1}^n\left({n\choose k}+{n\choose {k-1}}\right)x^{n+1-k}y^k+y^{n+1}\quad\quad\text{(distributivity and associativity laws in }R\text{)}\\ \end{array}$

Now, it follows from the recursive formula for binomial coefficients that

$\begin{array}{rcl} x^{n+1}+\sum_{k=1}^n\left({n\choose k}+{n\choose {k-1}}\right)x^{n+1-k}y^k+y^{n+1}&=&\binom {n+1}0x^{n+1}+\sum_{k=1}^n\binom{n+1}{k}x^{n+1-k}y^k+\binom {n+1}{n+1}y^{n+1}\\ &=&\sum_{k=0}^{n+1}\binom{n+1}{k}x^{n+1-k}y^k. \end{array}$

Thank you to the contributors under CC BY-SA 4.0!

Github:

### References

#### Bibliography

1. Forster Otto: "Analysis 1, Differential- und Integralrechnung einer VerĂ¤nderlichen", Vieweg Studium, 1983