1
$\begingroup$

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

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

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

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

Not the answer you're looking for? Browse other questions tagged .