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