Given $f(i, j) = f(i − 1, j − 1) + f(i, j − 1)$, find the value of $f(1009, 2019)$ 
Let $f:(\mathbb{N}\ \cup \{0\})^2$ $\rightarrow\mathbb{N}\ \cup\{0\}$ be such that $f(0, x) = f(x, 0) = 1$ for all x $\in$ $\mathbb{N}\ \cup$ {$0$}.
Also for all $i, j \in\ \mathbb{N}$ we have $f(i, j) = f(i − 1, j − 1) + f(i, j − 1)$. Find $f(1009, 2019)$.


What I've tried:
I took two cases: $i>=j$ and $i<j$.
As $j$ is reduced by $1$ in both $f(i-1,j-1)$ and $f(i,j-1)$, if $j<=i$, then $j$ will reach $0$ first irrespective of $i$. So the value of $f(i,j)$ is $2^{j}$. Here's a branch diagram to illustrate what I meant   
So $f(3,2)=2^2=4$
However I'm stuck at finding the pattern for the other case ($j>i$). Example for $f(i,j)$ where $i<j$:
$f(2,3)=7$
I do recognize that I can stop evaluating once I reach a point where $i=j$ but I can't find at which places and how many times they reach that point. It would be highly helpful If you would help me find the pattern. Also, am I going in the right direction? Is there any other way to solve this problem(a formula or something)? Help would be highly appreciable!
 A: Here is a generating function approach. We consider the recurrence relation
\begin{align*}
f(i,j)&=f(i-1,j-1)+f(i,j-1)\qquad\qquad i,j\geq 1\tag{1}\\
f(i,0)&=f(0,j)=1\qquad\qquad\qquad\qquad\qquad\quad i,j\geq 0
\end{align*}

We set
\begin{align*}
\color{blue}{F(x,y)=\sum_{i=0}^\infty\sum_{j=0}^\infty f(i,j)x^iy^j}
\end{align*}
and use guided from (1) the Ansatz
\begin{align*}
\sum_{i=1}^\infty\sum_{j=1}^\infty f(i,j) x^iy^j=\sum_{i=1}^\infty\sum_{j=1}^\infty f(i-1,j-1) x^iy^j+\sum_{i=1}^\infty\sum_{j=1}^\infty f(i,j-1) x^iy^j\tag{2}
\end{align*}

Left-hand side of (2):
We obtain
\begin{align*}
\sum_{i=1}^\infty&\sum_{j=1}^\infty f(i,j) x^iy^j\\
&=\sum_{i=0}^\infty\sum_{j=0}^\infty f(i,j) x^iy^j-\sum_{i=0}^\infty f(i,0)x^i-\sum_{j=0}^\infty f(0,j)y^j+f(0,0)\\
&=F(x,y)-\frac{1}{1-x}-\frac{1}{1-y}+1\tag{3}
\end{align*}
Right-hand side of (2):
We obtain
\begin{align*}
\sum_{i=1}^\infty&\sum_{j=1}^\infty f(i-1,j-1) x^iy^j+\sum_{i=1}^\infty\sum_{j=1}^\infty f(i,j-1) x^iy^j\\
&=\sum_{i=0}^\infty\sum_{j=0}^\infty f(i,j) x^{i+1}y^{j+1}+\sum_{i=1}^\infty\sum_{j=0}^\infty f(i,j) x^{i}y^{j+1}\\
&=xyF(x,y)+yF(x,y)-\sum_{j=0}^\infty f(0,j)y^{y+1}\\
&=xyF(x,y)+yF(x,y)-\frac{y}{1-y}\tag{4}
\end{align*}
From (3) and (4) we get:

\begin{align*}
F(x,y)-\frac{1}{1-x}-\frac{1}{1-y}+1&=xyF(x,y)+yF(x,y)-\frac{y}{1-y}\\
F(x,y)(1-y(1+x))&=\frac{1}{1-x}\\
\color{blue}{F(x,y)}&\color{blue}{=\frac{1}{1-x}\,\frac{1}{1-y(1+x)}}\tag{5}
\end{align*}

The final step is to extract $f(i,j)=[x^iy^j]F(x,y)$ where we use the coefficient of operator $[x^i]$ to denote the coefficient of $x^i$ of a series.

We obtain from (5) for $i,j\geq 0$:
\begin{align*}
\color{blue}{f(i,j)}&=[x^iy^j]\frac{1}{1-x}\,\frac{1}{1-y(1+x)}\\
&=[x^iy^j]\sum_{k=0}^\infty y^k(1+x)^k\,\frac{1}{1-x}\tag{6}\\
&=[x^i](1+x)^j\,\frac{1}{1-x}\tag{7}\\
&=[x^i](1+x)^j\sum_{k=0}^\infty x^k\tag{8}\\
&=\sum_{k=0}^i[x^{i-k}](1+x)^j\tag{9}\\
&=\sum_{k=0}^i\binom{j}{i-k}\tag{10}\\
&\color{blue}{=\begin{cases}
\sum_{k=0}^i\binom{j}{k}&\qquad j>i\\
2^j&\qquad j\leq i
\end{cases}}\tag{11}
\end{align*}

Comment:

*

*In (6) we use the geometric series expansion.


*In (7) we select the coefficient of $y^j$.


*In (8) we expand $\frac{1}{1-x}$.


*In (9) we use the linearity of the coefficient of operator and apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$. We also set the upper limit of the series to $i$ since other terms do not contribute.


*In (10) we selet the coefficient of $x^{i-k}$.


*In (11) we change the order of summation $k\to i-k$ and we use the binomial identity $\sum_{k=0}^j\binom{j}{k}=2^j$ as well as $\binom{j}{k}=0$ if $k>j$.
A: A slightly simpler solution based on VIVID's work (it's essentially the same).
If we utilize the generalized binomial coefficients where $$\binom{n}{k} = 0, n, k \in \mathbb Z, k > n \text { or } k<0$$ then VIVID's formula becomes $$f(m,n) = \sum_{k=0}^m \binom{n}{k} \tag 1$$
We also know the following recursive relation is true for these generalized coefficients as well:
$$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} \tag 2$$
Then, since $f$ is uniquely determined by $$f(0,x)=f(x,0)=1 \tag 3$$ and $$f(i, j) = f(i − 1, j − 1) + f(i, j − 1) \tag 4$$
we only need to show $(3)$ and $(4)$ are true when we plug in VIVID's formula $(1)$. Now, $(3)$ is obviously true. For $(4)$, indeed we have (via $(2)$)
$$f(i,j) = \sum_{k=0}^i \binom{j}{k} = \sum_{k=0}^i \binom{j-1}{k-1} + \sum_{k=0}^i \binom{j-1}{k}  \\
= \sum_{k=1}^i \binom{j-1}{k-1} + f(i,j-1)\\
= \sum_{k=0}^{i-1} \binom{j-1}{k} + f(i,j-1)\\
= f(i-1,j-1) + f(i,j-1).\blacksquare $$
