Question

Explain how to prove Pascal’s identity using a combinatorial argument.

Short answer

To prove Pascal’s identity using a combinatorial argument use the formula$\left(\begin{array}{c}\mathrm{n}\\ \mathrm{k}\end{array}\right)=\left(\begin{array}{c}\mathrm{n}-1\\ \mathrm{k}-1\end{array}\right)+\left(\begin{array}{c}\mathrm{n}-1\\ \mathrm{k}\end{array}\right)\forall 1\le \mathrm{k}\le \mathrm{n}.$ .

Step-by-step solution

Concept Introduction

Pascal's triangle is a triangular array of binomial coefficients found in probability theory, combinatorics, and algebra in mathematics.

Pascal’s Identity using Combinatorial Argument

Suppose there is an urn full of n number of distinguishable balls. If one has to pick exactly k number of balls out of this urn then the number of different ways in which this can be done can be calculated using two different methods.

First method: Pick any k number of balls out of the urn. Count the number of ways in which this can be performed which is $\left(\begin{array}{c}\mathrm{n}\\ \mathrm{k}\end{array}\right)$.

Second method: Fix a specific ball inside the urn. When the k balls are chosen, this particular ball can or cannot be chosen. In the first case, total $\left(\mathrm{k}-1\right)$number of balls has to be chosen out of the remaining $\left(\mathrm{n}-1\right)$balls, while in the second case, all of the k balls must be chosen from the remaining balls.

Equating the total number of ways in both the methods one gets Pascal's identity –

$\left(\begin{array}{c}\mathrm{n}\\ \mathrm{k}\end{array}\right)=\left(\begin{array}{c}\mathrm{n}-1\\ \mathrm{k}-1\end{array}\right)+\left(\begin{array}{c}\mathrm{n}-1\\ \mathrm{k}\end{array}\right)\forall 1\le \mathrm{k}\le \mathrm{n}$

Therefore, the result is obtained as$\left(\begin{array}{c}\mathrm{n}\\ \mathrm{k}\end{array}\right)=\left(\begin{array}{c}\mathrm{n}-1\\ \mathrm{k}-1\end{array}\right)+\left(\begin{array}{c}\mathrm{n}-1\\ \mathrm{k}\end{array}\right)\forall 1\le \mathrm{k}\le \mathrm{n}$.