Question

Use generating functions to prove Pascal's identity:

\(C(n,r) = C(n - 1,r) + C(n - 1,r - 1)\) when \(n\) and \(r\) are positive integers with \(r < n\).

Short answer

The resultant answer is \(C(n,r) = C(n - 1,r) + C(n - 1,r - 1)\).

Step-by-step solution

Given data

The given data is \(r\)and \(n\)are positive.

Concept of Extended binomial theorem

Generating function for the sequence \({a_0},{a_1}, \ldots ,{a_k}, \ldots \) of real numbers is the infinite series: \(G(x) = {a_0} + {a_1}x + {a_2}{x^2} + \ldots + {a_k}{x^k} + \ldots = \sum\limits_{k = 0}^{ + \infty } {{a_k}} {x^k}\)

Extended binomial theorem: \({(1 + x)^u} = \sum\limits_{k = 0}^{ + \infty } {\left( {\begin{array}{*{20}{l}}u\\k\end{array}} \right)} {x^k}\).

Use the binomial theorem and simplify the expression

Use the binomial theorem:

\(\begin{array}{l}{(1 + x)^{n - 1}} + x{(1 + x)^{n - 1}} = \sum\limits_{k = 0}^{ + \infty } {\left( {\begin{array}{*{20}{c}}{n - 1}\\k\end{array}} \right)} {x^k} + x\sum\limits_{k = 0}^{ + \infty } {\left( {\begin{array}{*{20}{c}}{n - 1}\\k\end{array}} \right)} {x^k}\\{(1 + x)^{n - 1}} + x{(1 + x)^{n - 1}} = \sum\limits_{k = 0}^{ + \infty } {\left( {\begin{array}{*{20}{c}}{n - 1}\\k\end{array}} \right)} {x^k} + \sum\limits_{k = 0}^{ + \infty } {\left( {\begin{array}{*{20}{c}}{n - 1}\\k\end{array}} \right)} {x^{k + 1}}\\{(1 + x)^{n - 1}} + x{(1 + x)^{n - 1}}\; = 1 + \sum\limits_{k = 1}^{ + \infty } {\left( {\begin{array}{*{20}{c}}{n - 1}\\k\end{array}} \right)} {x^k} + \sum\limits_{k = 1}^{ + \infty } {\left( {\begin{array}{*{20}{l}}{n - 1}\\{k - 1}\end{array}} \right)} {x^k}\\{(1 + x)^{n - 1}} + x{(1 + x)^{n - 1}} = 1 + \sum\limits_{k = 1}^{ + \infty } {\left( {\left( {\begin{array}{*{20}{c}}{n - 1}\\k\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{n - 1}\\{k - 1}\end{array}} \right)} \right)} {x^k}\end{array}\)

Since \({(1 + x)^n} = {(1 + x)^{n - 1}} + x{(1 + x)^{n - 1}}\)

\(\sum\limits_{k = 0}^{ + \infty } C (n,k){x^k} = 1 + \sum\limits_{k = 1}^{ + \infty } {\left( {\left( {\begin{array}{*{20}{c}}{n - 1}\\k\end{array}} \right) + \left( {\begin{array}{*{20}{l}}{n - 1}\\{k - 1}\end{array}} \right)} \right)} {x^k}\)

\(1 + \sum\limits_{k = 1}^{ + \infty } C (n,k){x^k} = 1 + \sum\limits_{k = 1}^{ + \infty } {\left( {\left( {\begin{array}{*{20}{c}}{n - 1}\\k\end{array}} \right) + \left( {\begin{array}{*{20}{l}}{n - 1}\\{k - 1}\end{array}} \right)} \right)} {x^k}\)

The corresponding coefficients then have to be equal (assuming \(k \ge 1\) ):

\(C(n,k) = C(n - 1,k) + C(n - 1,k - 1)\)

Let \(k = r\)and simplify the expression

Let \(k = r\) (assuming \(k = r \ge 1\) ):\(C(n,r) = C(n - 1,r) + C(n - 1,r - 1)\).

Hence, the resultant answer is \(C(n,r) = C(n - 1,r) + C(n - 1,r - 1)\).