Let $f(m,n)$ be the number of paths from $(0,0)$ to $(m,n)\in \mathbb{N}\times \mathbb{N}$, where each step is of the form $(1,0)$, $(0,1)$, or $(1,1)$.
a) Show that $\sum_{m\geq 0}\sum_{n\geq 0} f(m,n)x^my^n=(1-x-y-xy)^{-1}$.
**Here is what I have so far:
We can partition the set of paths from $(0,0)$ to $(m,n)$ into three sets: the set of paths that pass through the line $\overline{(m-1,n)(m,n)}$, the set of paths that pass through $\overline{(m,n-1)(m,n)}$, and the set of paths that pass through $\overline{(m-1,n-1)(m,n)}$. If we assume $f(m,n)=1$ if $m=0$ or $n=0$, our partition gives us the following recursion: $$f(m,n)= \left\{ \begin{array}{lr} 1 & \text{if}\, m=0 \, \, \text{or}\, \, n=0\\ f(m-1,n)+f(m,n-1)+f(m-1,n-1) &\hspace{-.9cm} \text{otherwise} \end{array} \right.. $$
Let $F(x,y)=\sum_{m\geq 0}\sum_{n\geq 0} f(m,n)x^my^n$. We have $$F(x,y)=\sum_{m\geq 0}\sum_{n\geq 0} f(m-1,n)x^my^n +\sum_{m\geq 0}\sum_{n\geq 0} f(m,n-1)x^my^n+ \sum_{m\geq 0}\sum_{n\geq 0} f(m-1,n-1)x^my^n$$ $$=x\sum_{m\geq 1}\sum_{n\geq 0} f(m-1,n)x^{m-1}y^n +y\sum_{m\geq 0}\sum_{n\geq 1} f(m,n-1)x^my^{n-1}+ xy\sum_{m\geq 1}\sum_{n\geq 1} f(m-1,n-1)x^{m-1}y^{n-1}$$ $$=xF(x,y)+yF(x,y)+xyF(x,y). $$ Thus far we have $$F(x,y)=xF(x,y)+yF(x,y)+xyF(x,y),$$ which gives us that $F(x,y)-xF(x,y)-yF(x,y)-xyF(x,y)=0$
Huh?? I must have done something wrong, but I can't see where! Any help at all is greatly appreciated. Thank you!
I would suggest you try
before applying the recurrence to the first part of this and then tidying up.
Since $f(0,0)=1$, you should then be able to avoid the "$=0$" at the end of your current working.