# Finding closed form of recurrence relation in two variables [closed]

I have a recurrence, $$F(n, m) = F(n-1, m) + F(n, m-1) + F(n-1,m-1)$$

$$F(n,1) = 0$$ $$F(1,n) = 2*(n-1)$$

I would like to compute $$F(N,M)$$ in terms of $$N$$ and $$M$$. The system is defined for $$1 \leq n \leq N$$ and $$1 \leq m \leq M$$ where $$N$$ and $$M$$ are non-negative integers.
I have solved many linear recurrences in past, but this type of recurrence in two variables is new to me. I even researched but couldn't find any good research paper involving method of reducing recurrences in terms of variables.

The value of $$N$$ can be upto $$10^3$$ and value of $$M$$ is upto $$10^9$$.

## closed as off-topic by Stefan Kohl, Chris Godsil, András Bátkai, Francois Ziegler, Ben McKayOct 12 at 13:57

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Stefan Kohl, Chris Godsil, Ben McKay
If this question can be reworded to fit the rules in the help center, please edit the question.

$$F(n,m)=D(n,m-1)-D(n-1,m-1)$$ where $$D(n,m)$$ are the Delannoy numbers.
• Notice that $D(n,m-1)-D(n-1,m-1)=D(n,m-2)+D(n-1,m-2)$. The size of the latter for $n=10^3, m=10^9$ can be estimated to be of the order of 6500 digits. So it depends on what you mean by "calculate". If you want all the digits of a specific value in your range, the formula $D(m,n)=\sum_{k=0}^{k=\min(m,n)} \binom{m}{k} \binom{n}{k} 2^k$ seems to me within easy reach of a laptop, with the right package and smart program. – Yaakov Baruch Oct 11 at 11:25
• @J.Jack : In terms of calculating $\binom{m}{k}$ for $1\le m \le 10^9$ and $1\le k \le 1^3$ if would simply do $(m-k+1)/1\times(m-k+2)/2\times(m-k+3)/3\times\cdots$, if there is nothing else better. – Yaakov Baruch Oct 11 at 11:35
• @J.Jack Sure. I built a few terms based on the recurrence relation, but starting from a single $1$ at the apex, then looked up the central terms on OEIS and found the reference to Delannoy numbers, which satisfy your recurrence. Eyeballing the table at wikipedia it was clear that subtracting from the table a shifted one, would keep the recurrence while also meeting your initial conditions. – Yaakov Baruch Oct 11 at 13:23