Tricky two-dimensional recurrence relation

Question

I would like to obtain a closed form for the recurrence relation $$a_{0,0} = 1,~~~~a_{0,m+1} = 0\\a_{n+1,0} = 2 + \frac 1 2 \cdot(a_{n,0} + a_{n,1})\\a_{n+1,m+1} = \frac 1 2 \cdot (a_{n,m} + a_{n,m+2}).$$

Even obtaining a generating function for that seems challenging. Is there a closed form for the recurrence relation or at least for the generating function? Alternatively, is there a closed form for $a_{n,0}$?

Answer 1

For $n\geqslant0$ let $F_n(t)=\sum_{m\in\mathbb Z}a_{n,m}t^m$, where we are going to define $a_{n,m}$ for negative $m$ in such a way that $a_{n+1,m}=\frac{a_{n,m-1}+a_{n,m+1}}2$ for all $n\geqslant0$ and all $m\in\mathbb Z$ (so that $F_{n+1}(t)=\frac{t+t^{-1}}2F_n(t)$) and moreover the remaining requirements $a_{0,0}=1$, $a_{0,m}=0$ for $m>0$ and $a_{n+1,0}=2+\frac12(a_{n,0}+a_{n,1})$ hold. The latter are equivalent to $a_{n,-1}=4+a_{n,0}$ for all $n$. Eliminating all variables in favor of $a_{0,m}$ with $m<0$ then gives $a_{0,-1}=5$ and $a_{0,-m}=8m-4$ for $m>1$, so that $F_0(t)=\frac{(1+t^{-1})^3}{(1-t^{-1})^2}$. Then $$ F_n(t)=\left(\frac{t+t^{-1}}2\right)^n\frac{(1+t^{-1})^3}{(1-t^{-1})^2}. $$ Expanding into powers of $t^{-1}$ gives (for $m\geqslant0$) $$ a_{n,m}=2^{-n}\left((3-2(-1)^{n+m})\binom n{\lfloor\frac{n-m}2\rfloor}+4\sum_{k=1}^{\lfloor\frac{n-m}2\rfloor}(4k-(-1)^{n+m})\binom n{\lfloor\frac{n-m}2\rfloor-k}\right). $$ Must be summable, giving in particular the expressions by Per Alexandersson. At any rate, the generating function for $a_{n,0}$ is given by \begin{multline*} \sum_{n=0}^\infty a_{n,0}t^n=\frac{1+t}{1-t}\left(\sqrt{\frac{1+t}{1-t}}-1\right)/t\\=(3\cdot1-2)+(9\cdot\frac12-2)t+(11\cdot\frac12-2)t^2+(17\frac{1\cdot3}{2\cdot4}-2)t^3+(19\frac{1\cdot3}{2\cdot4}-2)t^4\\+(25\frac{1\cdot3\cdot5}{2\cdot4\cdot6}-2)t^5+(27\frac{1\cdot3\cdot5}{2\cdot4\cdot6}-2)t^6\\+...+\left((8n+1)\frac{1\cdot3\cdot...\cdot(2n-1)}{2\cdot4\cdot...\cdot2n}-2\right)t^{2n-1}+\left((8n+3)\frac{1\cdot3\cdot...\cdot(2n-1)}{2\cdot4\cdot...\cdot2n}-2\right)t^{2n}+... \end{multline*}

Answer 2

Here is the table for $a_{n,m}2^m$ (since these are integers):

$$\begin{pmatrix} 1 & 5 & 14 & 35 & 82 & 186 & 412 & 899 & 1938 \\ 0 & 1 & 5 & 15 & 40 & 98 & 231 & 527 & 1180 \\ 0 & 0 & 1 & 5 & 16 & 45 & 115 & 281 & 660 \\ 0 & 0 & 0 & 1 & 5 & 17 & 50 & 133 & 336 \\ 0 & 0 & 0 & 0 & 1 & 5 & 18 & 55 & 152 \\ 0 & 0 & 0 & 0 & 0 & 1 & 5 & 19 & 60 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 5 & 20 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 5 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}$$

The top row does not give a hit in OEIS, but I conjecture that it is given by the following:

$$ a_{n,0} = \frac{(4 n+3) \Gamma \left(\frac{n+1}{2}\right)}{\sqrt{\pi } \Gamma \left(\frac{n}{2}+1\right)}-2 $$ if $n$ is even, and $$a_{n,0} = \frac{(4n+5) \Gamma \left(\frac{n}{2}+1\right)}{\sqrt{\pi } \Gamma \left(\frac{n+3}{2}\right)}-2 $$ if $n$ is odd.

Answer 3

1. Set $b_{n,m}=2^na_{n,m}$ if $m\geq 0$, and set $b_{n,m}=b_{n,-m-1}$ if $m<0$. Then the relation simplify to $$ b_{0,m}=f(m), \quad b_{n+1,m}=b_{n,m-1}+b_{n,m+1}+2^{n+2}f(m), $$ where $f(0)=f(-1)=1$, $f(m)=0$ otherwise.

2. Now define $c_{n,m}$ in the same way, but without a constant term: $$ c_{0,m}=f(m), \quad c_{n+1,m}=c_{n,m-1}+c_{n,m+1}. $$ Then it is clear that $c_{n,m}={n\choose \lfloor \frac{n-m}2\rfloor}$, where ${a\choose b}=0$ if $b\notin[0,a]$. On the other hand, the constant terms in the relations for $b_{n,m}$ merely add some more multiples of the $c_{i,m}$, so that $$ b_{n,m}=c_{n,m}+\sum_{0<k\leq n} 2^{k+1}c_{n-k,m}=-c_{n,m}+\sum_{0\leq k\leq n} 2^{k+1}c_{n-k,m}\\ =-{n\choose \lfloor \frac{n-m}2\rfloor}+2\sum_{0\leq k\leq n-m} 2^k{n-k\choose \lfloor \frac{n-k-m}2\rfloor}. $$

If $m=0$, ths simplifies as $$ b_{n,0}=-{n\choose \lfloor \frac{n}2\rfloor} +2\sum_{0\leq k\leq n/2}2^{2k}{n-2k\choose \lfloor \frac{n-2k}2\rfloor} +2\sum_{0\leq k\leq (n-1)/2}2^{2k+1}{n-2k-1\choose \lfloor \frac{n-2k-1}2\rfloor}. $$ Recall that ${2a\choose a}=2{2a-1\choose a-1}$, so these sums are almost the same.

Say, if $n$ is even, then $$ b_{n,0}=-{n\choose \frac{n}2}-2^{n+1} +4\sum_{0\leq k\leq n/2}2^{2k}{n-2k\choose \frac{n-2k}2} =-{n\choose \frac{n}2}-2^{n+1}+4\frac{(n+1)!}{\frac{n}2!^2} $$ (for the last sum, see Philippe Deléham's comment at http://oeis.org/A002457). Simplifying a bit, we get $$ b_{n,0}=(4n+3){n\choose \frac n2}-2^{n+1}, $$ which agrees with Per Alexandersson's formula.

The computation for odd $n$ is similar (one needs to separate the first term in the first sum of the general formula for $b_{n,0}$).