Course contentsShow
← Mathematics
Lesson 2604 of 3,12152. CombinatoricsFree lesson

Pascal's Identity and Recursive Properties

Prove Pascal's Identity C(n,k) = C(n-1,k-1) + C(n-1,k) and understand the recursive structure of binomial coefficients.

Pascal's Identity and Recursive Properties

You'll learn how binomial coefficients relate to each other through Pascal's Identity, revealing the elegant recursive structure hidden within combinations.

The Core Idea

Pascal's Identity states that any binomial coefficient can be expressed as the sum of two binomial coefficients from the previous row:

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

In plain English: The number of ways to choose k items from n items equals the sum of two scenarios: either you include a particular item (leaving k-1 to choose from the remaining n-1), or you exclude it (choosing all k from the remaining n-1).

Understanding the Proof

Think about selecting a committee of k people from n candidates. Focus on one specific person, say Alice:

  • Scenario 1: Alice is on the committee. Now you need k-1 more people from the remaining n-1 candidates. That's C(n-1, k-1) ways.

  • Scenario 2: Alice is NOT on the committee. You need all k people from the remaining n-1 candidates. That's C(n-1, k) ways.

Since every possible committee either includes Alice or doesn't (no overlap!), we add these: C(n, k) = C(n-1, k-1) + C(n-1, k).

The Recursive Structure

This identity explains why Pascal's Triangle works! Each entry is the sum of the two entries directly above it. It also provides a recursive definition for computing binomial coefficients:

  • Base cases: C(n, 0) = 1 and C(n, n) = 1
  • Recursive step: C(n, k) = C(n-1, k-1) + C(n-1, k)

This recursive property connects directly to the structure you've already seen in Pascal's Triangle and offers an alternative to the factorial formula for computation.

Key Takeaway: Pascal's Identity reveals that binomial coefficients have an inherent recursive structure where each coefficient is built from simpler ones, unifying the combinatorial interpretation with the geometric pattern of Pascal's Triangle.