Question

Show that if \(n\)and\(k\)are positive integers, then\(\left( {\begin{array}{*{20}{c}}{n + 1}\\k\end{array}} \right) = (n + 1)\left( {\begin{array}{*{20}{c}}n\\{k - 1}\end{array}} \right)/k\). Use this identity to construct an inductive definition of the binomial coefficients.

Short answer

Show that if \(n\)and\(k\)are positive integers, then\(\left( {\begin{array}{*{20}{c}}{n + 1}\\k\end{array}} \right) = (n + 1)\left( {\begin{array}{*{20}{c}}n\\{k - 1}\end{array}} \right)/k\). Use this identity to construct an inductive definition of the binomial coefficients.

Step-by-step solution

Given expression

Here,\(n\) and \(k\) are positive integers.

Definition of permutation and combination

\(P(n,r) = \frac{{n!}}{{(n - r)!}}\)Definition combination (order is not important):

\(C(n,r) = \left( {\begin{array}{*{20}{l}}n\\r\end{array}} \right) = \frac{{n!}}{{r!(n - r)!}}\)with\(n! = n \cdot (n - 1) \cdot \ldots \cdot 2 \cdot 1\)

Prove the given expression by the formula of permutation and combination

Use the formula of permutation and combination:

\(\begin{array}{c}\left( {\begin{array}{*{20}{c}}{n + 1}\\k\end{array}} \right) = \frac{{(n + 1)!}}{{k!((n + 1) - k)!}}\\ = \frac{{(n + 1)!}}{{k!(n + 1 - k)!}}\end{array}\)

\(\begin{array}{c}\left( {\begin{array}{*{20}{c}}{n + 1}\\k\end{array}} \right) = \frac{{(n + 1) \cdot n \cdot (n - 1) \cdot \ldots \cdot 2 \cdot 1}}{{k \cdot (k - 1) \cdot \ldots \cdot 2 \cdot 1 \cdot (n + 1 - k)!}}\\ = \frac{{(n + 1) \cdot n!}}{{k \cdot (k - 1)! \cdot (n + 1 - k)!}}\end{array}\)

\(\begin{array}{c}\left( {\begin{array}{*{20}{c}}{n + 1}\\k\end{array}} \right) = \frac{{n + 1}}{k} \cdot \frac{{n!}}{{(k - 1)! \cdot (n + 1 - k)!}}\\ = \frac{{n + 1}}{k} \cdot \frac{{n!}}{{(k - 1)! \cdot (n - (k - 1))!}}\end{array}\)

\(\left( {\begin{array}{*{20}{c}}{n + 1}\\k\end{array}} \right) = (n + 1)\left( {\begin{array}{*{20}{c}}n\\{k - 1}\end{array}} \right)/k\)

So,\(\left( {\begin{array}{*{20}{c}}{n + 1}\\k\end{array}} \right) = \frac{{n + 1}}{k} \cdot \left( {\begin{array}{*{20}{l}}n\\{k - 1}\end{array}} \right)\).