<s>[INST] 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}$?
 [/INST] 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*}
</s>