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:

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

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

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

    [math]x \approx y[/math] but would be very loose when [math]x << y[/math] or [math]y << x[/math].

    [math]f(x, y) \leq (1 + \sqrt{2})^{x+y}[/math]
     
    You can prove that this holds by induction. It clearly holds when [math]x=1[/math] or [math]y=1[/math]. For the induction:

    Let [math]\phi=1+\sqrt{2}[/math]

     [math]f(x, y) = f(x-1,y) + f(x-1, y-1)[/math] [math] + f(x, y-1)[/math]
    [math] \leq 2\phi^{x+y-1} + \phi^{x+y-2} [/math]
    [math] = \phi^{x+y} [/math]

    Side note: as always one guesses that value of [math]\phi[/math] by solving [math]\phi^2 = 2\phi + 1[/math]

Leave a Reply

Your email address will not be published. Required fields are marked *