Elementary combinatorics: Factorial and binomial coefficient
The binomium of Newton
We know the special product \[(a+b)^2=a^2+2ab+b^2\] Let's also work out \((a+b)^3\) and \((a+b)^4\).
Formulas for third and fourth powers of ( a + b ) \[\begin{aligned} (a+b)^3 &= (a+b)(a+b)^2 & \\[0.25cm] &= (a+b)(a^2+2ab+b^2) &\blue{\text{special product}}\\[0.25cm]&= a(a^2+2ab+b^2)+b(a^2+2ab+b^2) & \\[0.25cm]&=a^3+2a^2b+\phantom{2}ab^2 & \\[0.1cm] &\phantom{=a^3\,\,}+\phantom{2}a^2b+2ab^2 + b^3 & \\[0.25cm] &= a^3+3a^2b+3ab^2+b^3 & \\[0.5cm] (a+b)^4 &= (a+b)(a+b)^3 & \\[0.25cm] &=(a+b)(a^3+3a^2b+3ab^2+b^3) &\blue{\text{formula for }(a+b)^3}\\[0.25cm]&=\phantom{+}\!a(a^3+3a^2b+3ab^2+b^3) & \\[0.1cm] &\phantom{=}+b(a^3+3a^2b+3ab^2+b^3) &\\[0.25cm]&=a^4+3a^3b+3a^2b^2+\phantom{3}ab^3 & \\[0.1cm] &\phantom{=a^4\,\,}+\phantom{3}a^3b+3a^2b^2 + 3ab^3 +b^4& \\[0.25cm] &= a^4+4a^3b+6a^2b^2+4ab^3+b^4& \end{aligned}\]
Perhaps you already recognise a pattern in the formulas \[\begin{aligned}(a+b)^2&=a^2+2ab+b^2\\[0.25cm] (a+b)^3&=a^3+3a^2b+3ab^2+b^3\\[0.25cm] (a+b)^4&= a^4+4a^3b+6a^2b^2+4ab^3+b^4\end{aligned}\] with the terms systematically arranged according to descending powers of \(a\) and increasing powers of \(b\). The integers in front come from Pascal's triangle: \[\blue{\begin{array}{lccccccccccccc}
n=0\rightarrow\phantom{abc} &&&&&&&1&&&&&&\\[0.2cm]
n=1\rightarrow\phantom{abc} &&&&&&1&&1&&&&&\\[0.2cm]
n=2\rightarrow\phantom{abc} &&&&&1&&2&&1&&&&\\[0.2cm]
n=3\rightarrow\phantom{abc} &&&&1&&3&&3&&1&&&\\[0.2cm]
n=4\rightarrow\phantom{abc} &&&1&&4&&6&&4&&1&&\\[0.2cm]
n=5\rightarrow\phantom{abc} &&1&&5&&10&&10&&5&&1&\\[0.2cm]
n=6\rightarrow\phantom{abc} &1&&6&&15&&20&&15&&6&&1\\[0.2cm]
\ldots &&&&&&&\ldots&&&&&&&
\end{array}}\] They are binomial coefficients! So there is the following calculationrule, known as the binomium of Newton.
Binomium of Newton For all numbers \(a, b\) and \(n\in\mathbb{N}\) we have: \[\begin{aligned} (a+b)^n&=\binom{n}{0}a^n+\binom{n}{1}a^{n-1}b+\cdots + \binom{n}{n-1}ab^{n-1}+\binom{n}{n}b^{n}\\[0.25cm] &= \sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k\end{aligned}\]
Result 1 Choose \(a=b=1\) in the binomium of Newton and you get: \[\sum_{k=0}^{n}\binom{n}{k}=2^n\]
Corollary 1 Choose \(a=x, b=1\) in the binomium of Newton and you get: \[\sum_{k=0}^{n}\binom{n}{k}x^k=(1+x)^n\] When you differentiate both sides of the equation by \(x\), you get \[\sum_{k=0}^{n}\binom{n}{k}kx^{k-1}=n(1+x)^{n-1}\] Substituting \(x=1\) yields the following equality: \[\sum_{k=0}^{n}\binom{n}{k}k=n2^{n-1}=\tfrac{1}{2}n\,2^n\]