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 McKay Oct 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.

up vote 2 down vote accepted

$F(n,m)=D(n,m-1)-D(n-1,m-1)$ where $D(n,m)$ are the Delannoy numbers.

  • I wouldn't call this formula "closed form", but it shifts to the problem to a well known object. – Yaakov Baruch Oct 11 at 10:13
  • Hi, I went through link, and find it useful. but n can be upto 1e9, how can i calcaulate nCk for that ? – J.Jack Oct 11 at 10:52
  • 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
  • 1
    @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

Not the answer you're looking for? Browse other questions tagged or ask your own question.