Introduction

The recurrence f(m, n) = f(m - 1, n) + f(m, n - 1) appears in combinatorics, dynamic programming, and grid-path counting problems. The closed form depends on the boundary conditions, but with the standard base cases f(0, n) = 1 and f(m, 0) = 1, the solution becomes a binomial coefficient.

Start with the Boundary Conditions

A recurrence by itself is not enough to determine a unique formula. You also need starting values. The most common version of this problem assumes:

• 'f(0, n) = 1 for all n >= 0'
• 'f(m, 0) = 1 for all m >= 0'

That means the top row and left column of the grid are filled with ones. Every interior value is the sum of the cell above and the cell to the left.

If you write out a few values, you quickly get:

11   1   1   1
21   2   3   4
31   3   6  10
41   4  10  20

This is Pascal-style growth in two dimensions. The numbers match binomial coefficients, which is the main clue to the closed form.

Closed Form: A Binomial Coefficient

With those boundary conditions, the formula is:

f(m, n) = C(m + n, m) = C(m + n, n)

In plain words, choose m positions for one kind of step out of m + n total steps.

Why does that formula fit? Because binomial coefficients satisfy Pascal's identity:

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

If you substitute r = m + n and k = m, you get:

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

Now rewrite those two terms as:

• 'C((m - 1) + n, m - 1) = f(m - 1, n)'
• 'C(m + (n - 1), m) = f(m, n - 1)'

That matches the recurrence exactly.

Combinatorial Interpretation

A simple way to remember the formula is to interpret f(m, n) as the number of ways to move from (0, 0) to (m, n) on a grid if each move is either one step right or one step up.

Any valid path contains:

• exactly m right moves
• exactly n up moves

So every path is just an arrangement of m + n moves, where you choose which m positions are the right moves. That count is exactly C(m + n, m).

This interpretation also explains the recurrence. To reach (m, n), the final move must come either from (m - 1, n) or from (m, n - 1). Therefore the total count is the sum of those two smaller counts.

Compute It by Dynamic Programming

Even when the closed form is known, a dynamic programming table is still useful for understanding and testing the recurrence.

1def build_table(m, n):
2    dp = [[0] * (n + 1) for _ in range(m + 1)]
3
4    for i in range(m + 1):
5        dp[i][0] = 1
6    for j in range(n + 1):
7        dp[0][j] = 1
8
9    for i in range(1, m + 1):
10        for j in range(1, n + 1):
11            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
12
13    return dp
14
15
16table = build_table(3, 3)
17for row in table:
18    print(row)

That program prints:

1[1, 1, 1, 1]
2[1, 2, 3, 4]
3[1, 3, 6, 10]
4[1, 4, 10, 20]

The pattern makes the binomial structure obvious.

Compute the Closed Form Directly

Once you know the formula, direct computation is shorter:

1from math import comb
2
3def f(m, n):
4    return comb(m + n, m)
5
6
7print(f(2, 2))
8print(f(3, 4))

This is often the cleanest implementation when the boundary conditions match the standard version exactly.

What Changes if the Base Cases Change

The closed form above is not universal. If the boundary values are different, the answer changes. For example, if f(0, n) and f(m, 0) are not all ones, then the final table is no longer the standard Pascal grid.

That is why the first thing to ask in any recurrence problem is not "what is the formula" but "what are the initial conditions." Without those, several different functions could satisfy the same recurrence.

Common Pitfalls

• Trying to solve the recurrence without specifying the boundary conditions.
• Forgetting that the formula C(m + n, m) assumes f(0, n) = 1 and f(m, 0) = 1.
• Mixing up substring-style dynamic programming intuition with combinatorial path counting.
• Using factorial formulas directly for large values without considering overflow.
• Treating the recurrence as one-dimensional when it really lives on a grid.

Summary

• The recurrence f(m, n) = f(m - 1, n) + f(m, n - 1) needs boundary conditions to have a unique solution.
• With f(0, n) = 1 and f(m, 0) = 1, the closed form is C(m + n, m).
• The same result follows from Pascal's identity and from counting grid paths.
• Dynamic programming is a good way to verify the recurrence and visualize the pattern.
• Always check the initial conditions before claiming a closed form.