I have been given a recursive relation $$f(m,n)=f(m−1,n)+f(m,n−1)$$ in which I need to prove by mathematical induction that, $$f(m, n) = {(m + n)!\over(m!n!)}$$ over all natural numbers where $$f(0, n) = 1,\ f(m,0) = 1,\text{and } m,n \gt 0$$
I have done induction before, but I'm having a hard time grasping how to solve this recursive equation with two variables. Any help will be greatly appreciated!
Edit:
I forgot to add where I got to. I have solved for the base cases where $m = 1$ and $n = 1$.
$$f(1,1) = f(1-1,1)+f(1,1-1) \\ f(1,1) = f(0,1)+f(1,0) \\ f(1,1) = 1+1 \\ f(1,1) = 2$$
which equals (I'm calling the other function $g$)
$$g(1,1) = {(1+1)!\over(1!1!)} \\ g(1,1) = {2\over1} \\ g(1,1) = 2$$
$$f(1,1) = g(1,1)$$
This all checks out, but this is where I am stuck, I'm not sure how to do the induction step with two variables.
I am going to assume (inferred from the OP) that we have the recursive relation $$ f(m,n)=f(m-1,n)+f(m,n-1) $$
Consider the following table for $f(m,n)$ $$ \begin{array}{c|c} (m,n)&0&1&2&3&...&n-1&n\\ \hline 0&1&1&1&1&1&1&1\\ 1&1&2&3&4&...&\vdots&\vdots\\ 2&1&3&6&...&...&\vdots&\vdots\\ 3&1&4&...&...&...&\vdots&\vdots\\ \vdots&1&...&...&...&...&\vdots&\vdots\\ m-1&1&...&...&...&...&\vdots&f(m-1,n)\\ m&1&...&...&...&...&f(m,n-1)&f(m,n)\\ \end{array} $$ Suppose now that $f(m-1,n)=\frac{(m-1+n)!}{(m-1)!n!}$ and $f(m,n-1)=\frac{(m+n-1)!}{m!(n-1)!}$. Then note that $$ \begin{align} f(m,n)&=f(m-1,n)+f(m,n-1)\\ &=\frac{(m-1+n)!}{(m-1)!n!}+\frac{(m+n-1)}{m!(n-1)!}\\ &=\frac{(m-1+n)!m+(m+n-1)!n}{m!n!}\\ &=\frac{(m+n)!}{m!n!} \end{align} $$ and consider why this is enough to inductively fill the entire table ...