Closed form solution for recurrence relation with 2 variables

Question

Please help me in finding the closed form solution for the recurrence relation : \begin{align*} f(n, d) &= 2 \sum\limits_{i=1}^{n-1} f(i, d-1) + f(n, d-1) \\ & \text{for $n > 1, d > 1$} \\ f(n, 1) &= 2n-1\\ f(1, d) &= 1 \end{align*} I have no idea about how to solve this.
Thanks!

Answer 1

It never hurts to calculate a few values to get an idea of what’s going on:

$$\begin{array}{c|cc} n\backslash d&1&2&3&4\\ \hline 1&1&1&1&1\\ 2&3&5&7&9\\ 3&5&13&25&41\\ 4&7&25&63&129\\ 5&9&41&129&321 \end{array}$$

This table looks symmetric about the diagonal, or rather, it would if there were an initial $d=0$ column of ones. In fact, the $d=1$ column could then be calculated from the $d=0$ column by the same recurrence that we already have. Finally, it makes sense to shift the row indices down by $1$ to match the column indices:

$$\begin{array}{c|cc} n\backslash d&0&1&2&3&4\\ \hline 0&1&1&1&1&1\\ 1&1&3&5&7&9\\ 2&1&5&13&25&41\\ 3&1&7&25&63&129\\ 4&1&9&41&129&321 \end{array}\tag{1}$$

This table is for $a(n,d)$, where $n,d\ge 0$, $a(0,n)=a(n,0)=1$, and

$$a(n+1,d+1)=2\sum_{k=0}^na(k,d)+a(n+1,d)\;,$$

so that $f(n,d)=a(n-1,d)$.

If you stare at the second table for a bit, you may notice that each entry appears to be the sum of the entry to its left, the entry above it, and the entry immediately above and to its left; for instance, $129=63+41+25$. This suggests that we may have a simpler recurrence here:

Claim: $a(n+1,d+1)=a(n+1,d)+a(n,d)+a(n,d+1)$ for all $n,d\ge 0$.

Proof:

$$\begin{align*} a(n+1,d+1)&=a(n+1,d)+2\sum_{k=0}^na(k,d)\\ &=a(n+1,d)+2\sum_{k=0}^{n-1}a(k,d)+2a(n,d)\\ &=a(n+1,d)+a(n,d)+2\sum_{k=0}^{n-1}a(k,d)+a(n,d)\\ &=a(n+1,d)+a(n,d)+a(n,d+1)\;. \end{align*}$$

In fact, if we agree that $a(n,d)=0$ whenever $n<0$ or $d<0$, we can simply set $a(0,0)=1$ and derive all other values from the new recurrence. (By the way, it’s easy now to verify the symmetry $a(n,d)=a(d,n)$ that we noticed initially.)

If you rotate the array 45° clockwise, it looks a bit like the usual isosceles form of Pascal’s triangle, except that each entry is the sum of the nearest numbers above and to the left, above and to the right, and directly above:

$$\begin{array}{ccc} &&&&&&1\\ &&&&&1&&1\\ &&&&1&&3&&1\\ &&&1&&5&&5&&1\\ &&1&&7&&13&&7&&1\\ &1&&9&&25&&25&&9&&1\\ 1&&11&&41&&63&&41&&11&&1 \end{array}$$

If you enter the first five rows of that triangle into OEIS, you get three hits, of which the first proves to be exactly what’s wanted: we have OEIS A008288, and $(1)$ is the square array of Delannoy numbers, and the OEIS entry has numerous references and links. The Wikipedia entry offers the formulas

$$a(n,d)=\sum_k\binom{n+d-k}n\binom{d}k\;,\tag{2}$$

where the non-zero terms are those for which $0\le k\le\min\{n,d\}$.

To prove all this, first verify that $a(n,d)$ really is the number of lattice paths from $\langle 0,0\rangle$ to $\langle n,d\rangle$ using only unit steps to the east, to the north, and to the northeast; this is easily done by induction using the recurrence in the Claim. Then, as in the Wikipedia article, observe that if you use $k$ diagonal (northeast) steps, you must use $n-k$ steps to the east and $d-k$ to the north. These $n+d-k$ steps can be made in any order, so there are

$$\binom{n+d-k}{k,n-k,d-k}=\binom{n+d-k}n\binom{n}k$$

ways to make them. Summing over $k$ yields $(2)$.

Row (or column) $n$ of $(1)$ is given by a polynomial of degree $n$, but I don’t know of an actual closed form for these numbers (meaning one that does not involve a summation).