Lesson 11

It turns out that in the \(n\)-th row of Pascal's triangle are the coefficients obtained when expanding the brackets in the expression \((a+b)^{n}\). For example, in the second row, the numbers \(1, 2, 1\) are written, in the third row — \(1, 3, 3, 1\), in the fourth — \(1, 4, 6, 4, 1\): \[\begin{align*}(a+b)^{2}&=a^{2}+2ab+b^{2}\\ (a+b)^{3}&=a^{3}+3a^{2}b+3ab^{2}+b^{3}\\ (a+b)^{4}&=a^{4}+4a^{3}b+6a^{2}b^{2}+4ab^{3}+b^{4}\end{align*}\]

In general form: \[(a+b)^{n}=\binom{n}{0}a^{n}+\binom{n}{1}a^{n-1}b+\dotsm+\binom{n}{k}a^{n-k}b^{k}+\dotsb+\binom{n}{n}b^{n} \ .\] This formula is called the Newton binomial formula. And yes, that's why \(\binom{n}{k}\) is called the binomial coefficient: it is the coefficient of \(x^{k}\) in the \(n\)-th power of the binomial \((1+x)\). In a more compact form, it looks like this: \[(a+b)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k} \ .\] One way to prove it is to expand the brackets in the expression \[(a+b)(a+b)\dotsm(a+b) \ .\] The coefficient of \(a^{n-k}b^{k}\) will be exactly the number of ways to choose \(k\) brackets from which we take \(b\), that is, exactly \(\binom{n}{k}\).

The example below shows that the Newton binomial formula is also convenient for the power of the sum of two formal variables with coefficients. \[\begin{align*}(2a-b)^{4}&=\\&=((2a)+(-b))^{4}=\\&=(2a)^{4}+4(2a)^{3}(-b)+6(2a)^{2}(-b)^{2}+ 4(2a)(-b)^{3}+(-b)^{4}=\\&=16a^{4}-32a^{3}b+24a^{2}b^{2}-8ab^{3}+b^{4}\end{align*}\]

The Newton binomial formula has many remarkable consequences (or reformulations of properties we already know).

• Pascal's Rule:  \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\). The number \(\binom{n}{k}\) is the coefficient of \(x^{k}\) in the polynomial \((1+x)^{n}=(1+x)^{n-1}(1+x)=(1+x)^{n-1}+x(1+x)^{n-1}\).


• Sum in a row:  \(2^{n}=\sum_{k=0}^{n}\binom{n}{k}\). It is enough to substitute \(a=b=1\) into the binomial.


• Alternating sum:  \(\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}= 0\) (for \(n>0\)). It is enough to substitute \(a=1,b=-1\).


• Words in a three-letter alphabet:  \(3^{n}=\binom{n}{0}+\binom{n}{1}2+\binom{n}{2}2^{2}+\dotsm+\binom{n}{n}2^{n}\). It is enough to substitute \(a=1\), \(b=2\). A combinatorial proof: \(3^{n}\) is the number of words of length \(n\) over the alphabet \(\{x, y, z\}\), \(\binom{n}{k}2^{k}\) is the number of words of length \(n\), in which there are exactly \(n-k\) letters \(x\).


• Teams with the captain:  Differentiating the formula \((1+x)^{n}=\sum_{k=0}^{n}\binom{n}{k}x^{k}\), we get the equality \(n(1+x)^{n-1}=\sum_{k=1}^{n}k\binom{n}{k}x^{k-1}\). Substituting \(x=1\), we get the formula \(\sum_{k=1}^{n}k \binom{n}{k}=n2^{n-1}\). A combinatorial proof of this formula: if we want to choose a team from \(n\) people and a captain in it, we can either first choose the team and then choose its captain, or first choose the captain and then choose any subset of the remaining \(n-1\) people as the other team members.