Tricky two-dimensional recurrence relation 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}$?
 A: 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*}
A: 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.
A: *

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

*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}$).
