30. [15] The function $f: \mathbb{Z}^{2} \rightarrow \mathbb{Z}$ satisfies
- $f(x, 0)=f(0, y)=0$, and
- $f(x, y)=f(x-1, y)+f(x, y-1)+x+y$
for all nonnegative integers $x$ and $y$. Find $f(6,12)$.
Answer:
77500

Solution: We claim $f(x, y)=\binom{x+y+2}{x+1}-(x+y+2)$. Indeed, the hypothesis holds true for our base cases $f(x, 0)$ and $f(0, y)$, and moreover,
$$
f(x-1, y)+f(x, y-1)+x+y=\binom{x+y+1}{x}+\binom{x+y+1}{x+1}-2(x+y+1)+x+y=\binom{x+y+2}{x+1}-(x+y+2) .
$$

Thus, the final answer is $\binom{20}{7}-20=77500$.
Here is a way to derive this formula from scratch. The idea is that the second condition harks back to the Pascal's triangle rule, sans some modifications. Write $f(x, y)=g(x, y)-x-y$, so then $g(0, t)=g(t, 0)=t$ and $g(x, y)=g(x-1, y)+g(x, y-1)+2$. Then, letting $g(x, y)=h(x, y)-2$ gives $h(x, y)=h(x-1, y)+h(x, y-1)$, which is exactly Pascal's rule. We are given the base cases $h(0, t)=h(t, 0)=t+2$, which is starting "inside" of Pascal's triangle, so $h(x, y)=\binom{x+y+2}{x+1}$.