# 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.

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:

$$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!

• Pascal's triangle :) Jan 5, 2021 at 17:51
• Did you mean $f:(\mathbb{N}\ \cup \{0\})^2 \rightarrow\mathbb{N}\ \cup\{0\}$? Jan 5, 2021 at 17:54
• @CyclotomicField yes, I will edit it Jan 5, 2021 at 17:56
• @jlammy Pascal's triangle would work when $j<i$. But when $i<j$ some of the branches would stop when they reach $(0,x)$ or $(x,0)$. Am I right? How do we account for that? Jan 5, 2021 at 18:00
• The connection to Pascal's triangle / binomial coefficients may be clearer if you write out a table of small values for $f(i,j)$. (It won't be as simple as $f(i,j)=\binom{i+j}{i}$, but the pattern may yet be apparent.) Jan 5, 2021 at 18:10

I programmed the sequence to see if there is any pattern. Below is the $$13 \times 13$$ matrix including enough initial values to notice the pattern to be proven by induction after all:

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
[1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79]
[1, 2, 4, 8, 15, 26, 42, 64, 93, 130, 176, 232, 299]
[1, 2, 4, 8, 16, 31, 57, 99, 163, 256, 386, 562, 794]
[1, 2, 4, 8, 16, 32, 63, 120, 219, 382, 638, 1024, 1586]
[1, 2, 4, 8, 16, 32, 64, 127, 247, 466, 848, 1486, 2510]
[1, 2, 4, 8, 16, 32, 64, 128, 255, 502, 968, 1816, 3302]
[1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1013, 1981, 3797]
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2036, 4017]
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2047, 4083]
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4095]
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]


So, the pattern I noticed is as follows: $$f(m,n) = \begin{cases} \displaystyle\sum\limits_{k=0}^{m} {n \choose k},\ \ m < n \\[1mm] 2^n, \qquad \ \ \ \ ~ m\ge n \end{cases}$$ Next, we should prove it by induction.

The case $$m < n$$ (which is more interesting since $$1009 < 2019$$):

$$\square$$ We have enough information for the base case (see the table above). Now assume that $$f(m-1,n-1) = \sum_{k=0}^{m-1}{n-1 \choose k}$$ and $$f(m,n-1) = \sum_{k=0}^{m}{n-1 \choose k}$$ are true.

We should show that $$f(m-1,n-1) + f(m,n-1) = f(m,n)$$ is found by the same formula; that is, we are to prove $$\sum_{k=0}^{m-1}{n-1 \choose k} + \sum_{k=0}^{m}{n-1 \choose k} = \sum_{k=0}^{m} {n \choose k}$$

Indeed, \begin{align} \sum_{k=0}^{m-1}{n-1 \choose k} + \sum_{k=0}^{m}{n-1 \choose k} &= \sum_{k=1}^{m}{n-1 \choose k-1} + {n-1\choose 0} + \sum_{k=1}^{m}{n-1 \choose k} \\[1mm] &= {n-1\choose 0} + \sum_{k=1}^{m}\left[{n-1 \choose k-1} +{n-1 \choose k}\right] \\[1mm] &\overset*= {n\choose 0} + \sum_{k=1}^{m}{n\choose k} \\[1mm] &= \sum_{k=0}^m {n\choose k} \end{align} where (*) denotes the Pascal's formula. $$\blacksquare$$

The case $$m \ge n$$:

$$\square$$ The base case and the induction hypothesis are analogous and the induction step is trivially proven by noting that $$\underbrace{2^{n-1}}_{f(m-1,n-1)}+\underbrace{2^{n-1}}_{f(m,n-1)} = \underbrace{2^n}_{f(m,n)}. \ \ \blacksquare$$

Finally, we note that $$\boxed{f(1009, 2019) = \sum_{k=0}^{1009}{2019 \choose k}}$$

• 1) One has $f(1,1)=f(0,0)+f(1,0)=2$ but $m=n=1$ in your sum formula gives $\sum_{k=0}^0 \binom{1}{k} = \binom{1}{0}=1$. This doesn't occur if the upper limit if $m$ rather than $m-1$, so you may wish to recheck this. 2) If you look along and below the diagonal, you seem to have powers of 2. In other words, $f(m,n)=2^m$ if $m\geq n$. Jan 6, 2021 at 2:47
• @Semiclassical 1) I seem to confuse the indexing. In my indexing $f(2,2) = f(1,1) + f(2,1) = 2$. 2) I thought that sum formula would deal with the powers of two as well. Jan 6, 2021 at 2:59
• One interesting remark from WolframAlpha: For the case of $n=2m+1$, one has $f(m,2m+1)=\sum_{k=0}^m \binom{2m+1}{k}=4^m$ (source). This includes $f(1009,2019)$ as the $m=1009$ case. Jan 6, 2021 at 3:09
• Upon reflection, this is simple: $$\sum_{k=0}^{m} \binom{2m+1}{k}=\sum_{k=m+1}^{2m+1} \binom{2m+1}{k}=\frac12 \sum_{k=0}^{2m+1}\binom{2m+1}{k}=2^{2m}.$$ Jan 6, 2021 at 3:18
• @VIVID Do you mean$$\sum_{k=1}^{m}\left[{n-1 \choose k-1} +{n-1 \choose k}\right]$$ in the last but third line? Also thank you for your help! Jan 6, 2021 at 10:35

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$$.

• Happy to see someone take the g.f. approach. (+1) Jan 6, 2021 at 16:19
• @Semiclassical: Many thanks for your nice comment and the credit. :-) Jan 6, 2021 at 16:26

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$$