Skip to main content

πŸ“˜ Unique Paths - Formal Proof

Why dp[i][j] = dp[i-1][j] + dp[i][j-1] is a mathematical certainty, not just a pattern

SERIES NAVIGATION

πŸ“˜ Unique Paths Series:

  1. The Discovery Journey - How humans naturally discover the solution
  2. Plain English Proof - Accessible logical reasoning
  3. πŸ“˜ Formal Proof (You are here) - Mathematical rigor and certainty
  4. When Reality Gets Messy - Adapting to obstacles
THE CLAIM WE'RE PROVING

For any cell (i,j) where i > 0 and j > 0:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

This is not just an observationβ€”it's a mathematical certainty that can be proven rigorously.

🎯 Setting Up The Proof​

First, we need to be precise about what we're claiming. Let me define our terms carefully, the way you would in a formal proof.

Definition 1 (The Grid)​

Let G be an m Γ— n grid where cells are indexed by coordinates (i,j) with 0 ≀ i < m and 0 ≀ j < n.

  • Cell (0,0) is the top-left corner (start)
  • Cell (m-1, n-1) is the bottom-right corner (end)

Definition 2 (Valid Path)​

A valid path P from (0,0) to (i,j) is a sequence of cells (cβ‚€, c₁, cβ‚‚, ..., cβ‚–) where:

  • cβ‚€ = (0,0) (starts at origin)
  • cβ‚– = (i,j) (ends at target)
  • For each consecutive pair of cells, we move either:
    • Exactly one step right (increasing j by 1), OR
    • Exactly one step down (increasing i by 1)

Definition 3 (dp function)​

Let dp[i][j] denote the number of distinct valid paths from (0,0) to (i,j).

πŸ“œ The Proof (by Partition Argument)​

THEOREM

For any cell (i,j) where i > 0 and j > 0, the number of paths to (i,j) equals the sum of paths to (i-1,j) and paths to (i,j-1).

Formally: dp[i][j] = dp[i-1][j] + dp[i][j-1]

Proof:​

Let S be the set of all valid paths from (0,0) to (i,j).

We need to count the cardinality of S, which is what dp[i][j] represents.

Step 1: Partition the set S​

I will partition S into two disjoint subsets based on the final move of each path:

  • Let A = {paths in S whose final move is DOWN}

    • The second-to-last cell is (i-1, j)

  • Let B = {paths in S whose final move is RIGHT}

    • The second-to-last cell is (i, j-1)
Cell (i,j) can be reached from:

    (i-1,j)
       ↓
     [i,j]  ← (i,j-1)

Set A: paths ending with ↓
Set B: paths ending with ←

Step 2: Prove A and B partition S​

To show A and B partition S, I must prove two things:

Claim 2a: A ∩ B = βˆ… (the sets are disjoint)​

PROOF OF CLAIM 2a

Suppose for contradiction that there exists a path P that belongs to both A and B.

This would mean P's final move is simultaneously:

  • DOWN (coming from i-1,j)
  • RIGHT (coming from i,j-1)

But a path's final move is uniquely determined by its second-to-last cell.

Since (i-1,j) β‰  (i,j-1) when both i > 0 and j > 0, we have a contradiction.

Therefore A and B are disjoint. ∎

Claim 2b: A βˆͺ B = S (every path belongs to one of the sets)​

PROOF OF CLAIM 2b

Consider any path P in S.

Since P ends at (i,j) and starts at (0,0) where i > 0 and j > 0, the path must have made at least one move.

Let the second-to-last cell in P be denoted as (i',j').

By the definition of valid moves, we must have either:

Case 1: (i',j') = (i-1,j)

  • The final move was DOWN by one row
  • Therefore P ∈ A

Case 2: (i',j') = (i,j-1)

  • The final move was RIGHT by one column
  • Therefore P ∈ B

These are the only two ways to reach (i,j) from an adjacent cell.

Therefore every path in S belongs to either A or B. ∎

PARTITION ESTABLISHED

Since A and B are disjoint and their union is S, we have successfully partitioned S.

Step 3: Count the elements in A​

Consider any path P in A. This path:

  • Goes from (0,0) to (i,j)
  • Its final move is from (i-1,j) to (i,j)

Key Insight: If we remove this final move, we get a path from (0,0) to (i-1,j).

Conversely: Any path from (0,0) to (i-1,j) can be extended by one DOWN move to create a path in A.

BIJECTION ESTABLISHED

This creates a bijection (one-to-one correspondence) between:

  • The set A (paths to (i,j) ending with DOWN)
  • The set of all paths from (0,0) to (i-1,j)

Since bijections preserve cardinality, we have:

|A| = number of paths from (0,0) to (i-1,j) = dp[i-1][j]

Step 4: Count the elements in B​

By identical reasoning, removing the final RIGHT move from any path in B gives us a bijection between:

  • The set B (paths to (i,j) ending with RIGHT)
  • The set of all paths from (0,0) to (i,j-1)

Therefore:

|B| = number of paths from (0,0) to (i,j-1) = dp[i][j-1]

Step 5: Apply the Addition Principle​

Since A and B partition S (they are disjoint and their union equals S), by the fundamental counting principle:

|S| = |A| + |B|

Substituting our results from Steps 3 and 4:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

This completes the proof. ∎

πŸ’‘ Why This Proof Matters (The Deeper Understanding)​

Now that you've seen the formal proof, let me explain why each step was necessary and what mathematical principles we relied on.

The Partition Principle​

FUNDAMENTAL THEOREM FROM COMBINATORICS

If you can partition a set into disjoint subsets, the total count is the sum of the counts of each subset.

This is sometimes called the Addition Principle or Rule of Sum.

Formally: If S = A₁ βˆͺ Aβ‚‚ βˆͺ ... βˆͺ Aβ‚™ and the sets Aα΅’ are pairwise disjoint, then:

|S| = |A₁| + |Aβ‚‚| + ... + |Aβ‚™|

We used the two-set case: S = A βˆͺ B where A ∩ B = βˆ….

Why this matters: We're not just guessing that addition works. We're using a proven theorem from set theory. This is why we can be certain that counting paths from two sources and adding them gives us the total.

The Bijection Principle​

In Step 3 and Step 4, I established bijections between sets. This is a powerful counting technique.

BIJECTION PRINCIPLE

If there exists a bijection f: X β†’ Y, then |X| = |Y|.

In our case:

  • X = paths to (i,j) whose final move is DOWN
  • Y = paths to (i-1,j)
  • The bijection is: "remove the final DOWN move" (with inverse "add a DOWN move")

Why this matters: This proves we're not overcounting or undercounting. Every path to (i-1,j) corresponds to exactly one path in A, and vice versa. There's a perfect one-to-one matching.

The Uniqueness of the Final Move​

This might seem obvious, but it's crucial: every path has exactly one final move, and that move is uniquely determined.

This is what made our partition possible. If a path could somehow arrive at (i,j) from multiple cells simultaneously, or if there were other ways to reach (i,j) besides from (i-1,j) or (i,j-1), our proof would fail.

CRITICAL CONSTRAINT

The constraint that we can only move RIGHT or DOWN is what guarantees this uniqueness.

🧱 Base Cases (Completing the Inductive Structure)​

You might notice our proof assumes i > 0 and j > 0. What about the edges of the grid?

Base Case 1: dp[0][0] = 1​

There is exactly one path from (0,0) to (0,0): the empty path that makes no moves.

This is our starting point, and it makes intuitive sense. You're already at the destination.

Base Case 2: For all j > 0, dp[0][j] = 1​

When i = 0, we're in the first row.

To reach (0,j), we cannot move DOWN (we're already at the top).

Therefore, every path must consist entirely of RIGHT moves. There is exactly one such path:

(0,0) β†’ (0,1) β†’ (0,2) β†’ ... β†’ (0,j)

Base Case 3: For all i > 0, dp[i][0] = 1​

By symmetrical reasoning, when j = 0, we're in the first column.

Every path must consist entirely of DOWN moves, and there is exactly one such path.

INDUCTIVE STRUCTURE

Now, with these base cases established, our recurrence relation gives us the ability to compute dp[i][j] for any cell in the grid through a process that resembles mathematical induction.

🎲 An Alternative Proof (Combinatorial Interpretation)​

Let me show you another way to prove the same result, which gives additional insight.

Observation​

Any path from (0,0) to (i,j) consists of:

  • Exactly i DOWN moves
  • Exactly j RIGHT moves
  • Total of (i+j) moves

Combinatorial Question​

In how many ways can we arrange i identical D's and j identical R's?

This is a classic combinatorics problem. We're choosing i positions out of (i+j) total positions to place the D's.

The answer is the binomial coefficient:

dp[i][j] = C(i+j, i) = (i+j)! / (i! Γ— j!)

Pascal's Identity​

There's a well-known identity for binomial coefficients called Pascal's Identity:

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

Applying this with n = i+j and k = i:

C(i+j, i) = C(i+j-1, i-1) + C(i+j-1, i)
THE CONNECTION

Notice that:

  • C(i+j-1, i-1) represents choosing (i-1) positions out of (i+j-1) total β†’ corresponds to a path to (i-1,j)
  • C(i+j-1, i) corresponds to a path to (i,j-1)

Therefore:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

This is the same recurrence relation, proven through a completely different approach using combinatorial identities!

πŸ€” Why Are There Two Different Proofs?​

This is an important meta-mathematical point. The fact that we can prove the same result in two fundamentally different ways tells us something deep.

TWO PERSPECTIVES, ONE TRUTH

First proof (partition argument):

  • Works directly with the paths themselves
  • Reasons about the structure of the problem
  • Every path must come from somewhere
  • We can classify paths by where they come from
  • First principles approach

Second proof (combinatorial counting):

  • Transforms the problem into a different domain (arranging symbols)
  • Uses known theorems about binomial coefficients
  • More elegant but relies on prior knowledge
  • Top-down approach using established results

Both are valid. Both give insight.

The first proof is more "first principles" because it builds directly from the definition of paths.

The second proof is more elegant but relies on prior knowledge of Pascal's Identity.

IN YOUR LEARNING JOURNEY

Seeing multiple proofs of the same statement is valuable because each proof illuminates different aspects of why something is true.

🧠 What Makes This Proof "Obvious" (In Hindsight)​

After working through the formal proof, you might think "well, of course it works that way."

But notice what you needed to see it:

PREREQUISITES YOU MIGHT HAVE TAKEN FOR GRANTED
  1. Understanding that sets can be partitioned
  2. Knowing that disjoint sets' cardinalities add
  3. Recognizing when two sets have the same size (bijection)
  4. Seeing that every path has a unique final move

These are not trivial insights! They're the result of mathematical training.

When someone says "it's obvious that dp[i][j] = dp[i-1][j] + dp[i][j-1]," what they really mean is:

"Once you understand partitioning, bijections, and the addition principle, the conclusion follows necessarily."

The proof makes the intuition rigorous. It transforms a pattern you observed into a logical certainty.

πŸ§ͺ Test Your Understanding​

VERIFY YOUR COMPREHENSION

Question 1: Breaking the Partition​

In our partition proof, we relied on the fact that A and B are disjoint.

Can you construct a scenario where, if we allowed diagonal moves, A and B would no longer partition the set S properly?

What would go wrong?

Click for answer

If we allowed diagonal moves, we'd need to add a third set:

  • C = paths whose final move is DIAGONAL (from i-1, j-1)

Now we'd need to partition into three disjoint sets: A, B, and C.

The formula would become:

dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]

The original proof structure still works! We just have three subsets instead of two.

The key is that the partition principle generalizes: as long as the sets are disjoint and cover all cases, we can add their cardinalities.

Question 2: The Inverse Function​

The bijection in Step 3 maps paths in A to paths to (i-1,j) by "removing the final move."

What is the inverse function, and why is it important that the inverse exists?

Click for answer

The inverse function: g: paths to (i-1,j) β†’ A

Defined as: "Take a path P to (i-1,j) and append one DOWN move to reach (i,j)"

Why it matters:

  1. For a function to be a bijection, it must be both injective (one-to-one) and surjective (onto)
  2. Having an inverse proves it's a bijection
  3. This guarantees every path in A corresponds to exactly one path to (i-1,j)
  4. No paths are double-counted or missed

Without the inverse, we couldn't be sure the mapping was one-to-one!

Question 3: Pascal's Identity Proof​

In the combinatorial proof, we used Pascal's Identity.

Can you prove Pascal's Identity itself using a partition argument similar to what we did for paths?

Hint: Think about choosing k items from n items. Partition based on whether a specific item is chosen or not.

Click for answer

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

Proof by Partition:

Let S be the set of all ways to choose k items from n items.

Pick a specific item, call it x.

Partition S based on whether x is chosen:

  • A = selections that include x
  • B = selections that exclude x

Count A: If x is included, we need to choose k-1 more items from the remaining n-1 items.

|A| = C(n-1, k-1)

Count B: If x is excluded, we choose all k items from the remaining n-1 items.

|B| = C(n-1, k)

Since A and B partition S:

C(n, k) = |A| + |B| = C(n-1, k-1) + C(n-1, k)

This is the exact same proof structure we used for paths! ∎

Question 4: Modifying the Rules​

If we modified the problem so that you could move RIGHT, DOWN, or stay in place (but you must eventually reach the end), would our recurrence relation still hold?

Why or why not? What would need to change in the proof?

Click for answer

No, the recurrence would NOT hold in its current form.

Why it breaks:

  1. If we can "stay in place," paths are no longer finite in length
  2. You could stay at (i,j) forever without reaching the end
  3. The number of paths becomes infinite

What would need to change:

If we add the constraint "you cannot stay in the same place twice in a row," then:

  • We'd need a 3D state: dp[i][j][last_move]
  • Where last_move can be: RIGHT, DOWN, or STAY
  • The recurrence becomes:
dp[i][j]["STAY"] = dp[i][j]["RIGHT"] + dp[i][j]["DOWN"]
dp[i][j]["RIGHT"] = dp[i][j-1]["RIGHT"] + dp[i][j-1]["DOWN"] + dp[i][j-1]["STAY"]
dp[i][j]["DOWN"] = dp[i-1][j]["RIGHT"] + dp[i-1][j]["DOWN"] + dp[i-1][j]["STAY"]

The partition principle still applies, but we partition based on both the previous cell and the previous move type!

🎯 Key Takeaways​

WHAT YOU SHOULD REMEMBER

  1. The Recurrence is Provable:

    • Not just an observation
    • Follows from set theory and counting principles

  2. Partition + Bijection = Counting:

    • Partition the set by the final move
    • Use bijections to count each partition
    • Add the counts (addition principle)

  3. Multiple Proof Approaches:

    • Direct (partition argument)
    • Combinatorial (binomial coefficients)
    • Both lead to the same truth

  4. Prerequisites Matter:

    • Understanding partitions, bijections, and addition principle
    • These aren't "obvious"β€”they're learned foundations

  5. Uniqueness of Final Move:

    • Critical to the partition working
    • Guaranteed by the movement constraints

πŸš€ Connection to Other Problems​

After understanding this proof:

  1. Minimum Path Sum - Same proof structure, different operation (min instead of +)
  2. Unique Paths II - Add guard condition for obstacles, proof structure survives
  3. Binomial Coefficients - Direct combinatorial connection via Pascal's Identity
  4. Edit Distance - 2D DP with similar partition logic (3 operations instead of 2 moves)

The proof technique generalizes far beyond this specific problem!

Remember: A proof doesn't just show that something is trueβ€”it reveals why it must be true. Understanding the proof gives you the power to adapt the solution when constraints change.