Calculus – Sequences and series – Pascal's triangle and the binomial theorem

Pascal's triangle is a triangular array of binomial coefficients:

\[\begin{array}{ccccccccccccccc} &&&&&&& 1\\[2.5mm] &&&&&& 1 && 1\\[2.5mm] &&&&& 1 && 2 && 1\\[2.5mm] &&&& 1 && 3 && 3 && 1\\[2.5mm] &&& 1 && 4 && 6 && 4 && 1\\[2.5mm] && 1 && 5 && 10 && 10 && 5 && 1\\[2.5mm] & 1 && 6 && 15 && 20 && 15 && 6 && 1\\[2.5mm] 1 && 7 && 21 && 35 && 35 && 21 && 7 && 1 \end{array}\]

In Pascal's triangle, each number is the sum of the two numbers directly above it. The triangle can be extended by adding rows below in the same pattern. In terms of binomial coefficients\({}^{(*)}\) this property can be written as

\[\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k},\quad k=1,2,3,\ldots,n\]

for positive integers \(n\).

Proof:
\begin{align*} \binom{n-1}{k-1}+\binom{n-1}{k}&=\frac{(n-1)!}{(k-1)!\,(n-k)!}+\frac{(n-1)!}{k!\,(n-k-1)!}=\frac{(n-1)!}{k!\,(n-k)!}\left[k+(n-k)\right]\\[2.5mm] &=\frac{n\,(n-1)!}{k!\,(n-k)!}=\frac{n!}{k!\,(n-k)!}=\binom{n}{k}. \end{align*}

Now the binomial theorem reads: \(\displaystyle(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k=\sum_{k=0}^n\binom{n}{k}a^kb^{n-k}\).

Proof:
By mathematical induction: for \(n=0\) it reads \((a+b)^0=1=\displaystyle\binom{0}{0}a^0b^0\) which is true by definition. Suppose that the formula is true for certain value of \(n\), then we have:

\begin{align*} (a+b)^{n+1}&=(a+b)(a+b)^n=(a+b)\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k=\sum_{k=0}^n\binom{n}{k}a^{n-k+1}b^k+\sum_{k=0}^n\binom{n}{k}a^{n-k}b^{k+1}\\[2.5mm] &=\sum_{k=0}^n\binom{n}{k}a^{n-k+1}b^k+\sum_{k=1}^{n+1}\binom{n}{k-1}a^{n-k+1}b^k=a^{n+1}+\sum_{k=1}^n\left\{\binom{n}{k}+\binom{n}{k-1}\right\}a^{n-k+1}b^k+b^{n+1}\\[2.5mm] &=a^{n+1}+\sum_{k=1}^n\binom{n+1}{k}a^{n+1-k}b^k+b^{n+1}=\sum_{k=0}^{n+1}\binom{n+1}{k}a^{n+1-k}b^k. \end{align*}

This implies that \((a+b)^0=1\), \((a+b)^1=a+b\), \((a+b)^2=a^2+2ab+b^2\), \((a+b)^3=a^3+3a^2b+3ab^2+b^3\), and so on.

Example: \((1+x)^7=1+7x+21x^2+35x^3+35x^4+21x^5+7x^6+x^7\).

The Fibonacci numbers appear in Pascal's triangle as follows:

This can be written as \(F_n=\displaystyle\sum_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n-k-1}{k}\) for \(n=1,2,3,\ldots\). Here \(\lfloor{\alpha}\rfloor\) denotes the greatest integer less than or equal to \(\alpha\). This is equivalent to

\[F_{2n-1}=\sum_{k=0}^{n-1}\binom{2n-k-2}{k}\quad\text{and}\quad F_{2n}=\sum_{k=0}^n\binom{2n-k-1}{k},\quad n=1,2,3,\ldots.\]

The proof is by mathematical induction. For \(n=1\) we have \(F_1=\displaystyle\binom{0}{0}=1\) and \(F_2=\displaystyle\sum_{k=0}^1\binom{1-k}{k}=\binom{1}{0}+\binom{0}{1}=1\). Now we assume that \(F_{2n-1}=\displaystyle\sum_{k=0}^{n-1}\binom{2n-k-2}{k}\) and \(F_{2n}=\displaystyle\sum_{k=0}^n\binom{2n-k-1}{k}\) for a certain value of \(n\), then we have \[\sum_{k=0}^n\binom{2n-k}{k}=1+\sum_{k=1}^n\binom{2n-k-1}{k}+\sum_{k=1}^n\binom{2n-k-1}{k-1} =\sum_{k=0}^n\binom{2n-k-1}{k}+\sum_{k=0}^{n-1}\binom{2n-k-2}{k}=F_{2n}+F_{2n-1}=F_{2n+1}\]

and

\[\sum_{k=0}^{n+1}\binom{2n-k+1}{k}=1+\sum_{k=1}^{n+1}\binom{2n-k}{k}+\sum_{k=1}^{n+1}\binom{2n-k}{k-1} =\sum_{k=0}^{n+1}\binom{2n-k}{k}+\sum_{k=0}^n\binom{2n-k-1}{k}=F_{2n+1}+F_{2n}=F_{2n+2}.\]

We also have \(F_{m+2n}=\displaystyle\sum_{k=0}^n\binom{n}{k}F_{m+k}\) for \(n=1,2,3,\ldots\).

The proof is by mathematical induction. For \(n=1\) we have: \(F_{m+2}=\displaystyle\sum_{k=0}^1\binom{1}{k}F_{m+k}=F_m+F_{m+1}\) which is true. Now we assume that \(F_{m+2n}=\displaystyle\sum_{k=0}^n\binom{n}{k}F_{m+k}\) for a certain value of \(n\). Then we have

\[\sum_{k=0}^{n+1}\binom{n+1}{k}F_{m+k}=F_m+\sum_{k=1}^{n+1}\left\{\binom{n}{k}+\binom{n}{k-1}\right\}F_{m+k} =\sum_{k=0}^n\binom{n}{k}F_{m+k}+\sum_{k=0}^n\binom{n}{k}F_{m+k+1}=F_{m+2n}+F_{m+2n+1}=F_{m+2n+2}.\] The special case \(m=0\) reads: \(F_{2n}=\displaystyle\sum_{k=0}^n\binom{n}{k}F_k\).

---

\({}^{(*)}\) If we define factorials as \(0!=1\) and \(n!=n(n-1)!\) for \(n=1,2,3,\ldots\), then the binomial coefficient \(\displaystyle\binom{n}{k}\) is defined as

\[\binom{n}{k}=\frac{n!}{k!(n-k)!}.\]

---

Last modified on March 22, 2021