# Is there a closed form expression for this 2D generalization of the Fibonacci sequence?

You've essentially described the Delannoy Numbers.  See http://www.research.att.com/~nja… for a list of references.

This isn't exactly a closed form, but here's a formula that might be helpful to you:

$f(x,y) = \sum_{d=0}^{\min\{x-1,y-1\}} 2^d \binom{x-1}{d}\binom{y-1}{d}.$

## One thought on “Is there a closed form expression for this 2D generalization of the Fibonacci sequence?”

1. Alon Amit says:

Although this doesn't solve the general problem, it gives you a simple upper-bound. I think the bound would be tight when

$x \approx y$ but would be very loose when $x << y$ or $y << x$.

$f(x, y) \leq (1 + \sqrt{2})^{x+y}$

You can prove that this holds by induction. It clearly holds when $x=1$ or $y=1$. For the induction:

Let $\phi=1+\sqrt{2}$

$f(x, y) = f(x-1,y) + f(x-1, y-1)$ $+ f(x, y-1)$
$\leq 2\phi^{x+y-1} + \phi^{x+y-2}$
$= \phi^{x+y}$

Side note: as always one guesses that value of $\phi$ by solving $\phi^2 = 2\phi + 1$