<s>[INST] $f(m, n) = f(m-1, n) + f(m, n-1) + f(m-1, n-1)$ show that $\sum_{n=0}^{\infty} f(n, n) x^n = \frac{1}{\sqrt{1 - 6x + x^2}}$ Problem Statement: Let $f(m, 0) = f(0, n) = 1$ and $f(m, n) = f(m-1, n) + f(m, n-1) + f(m-1, n-1)$ for $m, n > 0$. Show that
$$\sum_{n=0}^{\infty} f(n, n) x^n = \frac{1}{\sqrt{1 - 6x + x^2}}$$
I was able to figure out the generating function for $f(i, j)$ but not for $f(n, n)$ as shown below.
Let $F(x, y) = \sum_{i\geq 0}\sum_{j \geq 0} f(i, j)x^iy^j$ be the generating function for $f(i,j)$. By the recurrence we have
\begin{equation}
    F(x, y) - xF(x, y) - yF(x, y) - xyF(x, y) = 1
\end{equation}
so that $F(x, y) = \frac{1}{1 - x - y - xy}$.
Here I'm thinking that I should plug in appropriate values for $x$, and $y$. Naturally $x = y$ is the first thing that comes to mind but that doesn't give what we want. Any hints would be greatly appreciated!
 [/INST] Let
$$G(x,t)=F(xt,xt^{-1}).$$
Then
$$G(x,t)=\sum_{i,j}f(i,j)x^{i+j}t^{i-j}
=\sum_{r,s}f((r+s)/2,(r-s)/2)x^rt^s$$
so the terms with $t^0$ therein add to $\sum_r f(r,r)x^{2r}$, essentially what you're
after.
But
$$G(x,t)=\frac{1}{1-x^2-xt-xt^{-1}}$$
and
\begin{align}
1-x^2-xt-xt^{-1}&=
-xt^{-1}\left(t-\frac{1-x^2}{2x}+\frac{\sqrt{1-6x^2+x^4}}{2x}\right)
\left(t-\frac{1-x^2}{2x}-\frac{\sqrt{1-6x^2+x^4}}{2x}\right)\\
&=-xt^{-1}(t-u(x))(t-u(x)^{-1})\\
&=xu(x)^{-1}(1-u(x)t)(1-u(x)t^{-1})
\end{align}
where
$$u(x)=\frac{1-x^2}{2x}-\frac{\sqrt{1-6x^2+x^4}}{2x}$$
is actually a power series in $x$ with zero constant term.
This has a partial fraction expansion
$$G(x,t)=\frac{x^{-1}u(x)}{(1-u(x)t)(1-u(x)t^{-1})}=
\frac{x^{-1}}{u(x)^{-1}-u(x)}\left(\frac{1}{1-u(x)t}
+\frac{u(x)t^{-1}}{1-u(x)t^{-1}}\right).$$
The $t^0$ terms therein, are
$$\frac{x^{-1}}{u(x^{-1}-u(x)}=\frac1{\sqrt{1-6x^2+x^4}}.$$
Then
$$\sum_{n=0}^\infty f(n,n)x^{2n}=\frac1{\sqrt{1-6x^2+x^4}}.$$
</s>