Question

Prove that if\(n\)and\(k\)are integers with\(1 \le k \le n\), then\(k \cdot \left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right) = n \cdot \left( {\begin{array}{*{20}{l}}{n - 1}\\{k - 1}\end{array}} \right)\),

a) using a combinatorial proof. [Hint: Show that the two sides of the identity count the number of ways to select a subset with\(k\)elements from a set with n elements and then an element of this subset.]

b) using an algebraic proof based on the formula for\(\left( {\begin{array}{*{20}{l}}n\\r\end{array}} \right)\)given in Theorem\(2\)in Section\(6.3\).

Short answer

(a) By the use of combinatorial proof, \(k \cdot \left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right) = n \cdot \left( {\begin{array}{*{20}{l}}{n - 1}\\{k - 1}\end{array}} \right)\)is proved.

(b) By an algebraic proof, \(k \cdot \left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right) = n \cdot \left( {\begin{array}{*{20}{l}}{n - 1}\\{k - 1}\end{array}} \right)\)is proved.

Step-by-step solution

Formula of Pascal’s rule and the definition of combinatorial meaning of it

Pascal’s rule:

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

Pascal’s rule has an intuitive combinatorial meaning, that is clearly expressed in counting proof.Equal the number of subsets with\(k\)elements from a set with\(n\)elements. Suppose one particular element is uniquely labelled\(X\)in a set with\(n\)elements. Such subsets.

Use the combinatorial proof of Pascal’s law

a)

For \(1 \le k \le n\), consider a set\(s\)with\(n\)no. of elements, and count the no. of ways to select a \(k\)-subset of\(s\)and then an element of it.

First, select a particular subset of\(s\)with\(k\)elements in exactly \(\left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right)\) ways and then can select any element from this subset in\(k\)different ways.

Next, fix the element, say\(x\)and then select the other members of the\(k\)subset containing\(x\)from \(S - \{ x\} \) in exactly \(\left( {\begin{array}{*{20}{l}}{n - 1}\\{k - 1}\end{array}} \right)\) ways.

This process can be repeated for each of the\(n\)elements of\(s\).

The product rule indicates that the count of the same quantity in the above two different methods then what follows is:

\(k \cdot \left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right) = n \cdot \left( {\begin{array}{*{20}{l}}{n - 1}\\{k - 1}\end{array}} \right)\)

Use an algebraic proof with Pascal’s identity

b)

Use Pascal's identity:

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

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

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