Get explicit expression of $f(m,n)$

Question

$$ f( m,n) =\left\{ \begin{array}{l} 1&\text{ if } m=n=0;\\ 0&\text{ if } m\ne 0,\ n=0;\\ \displaystyle\sum_{t\in \left\{ -1,0,1 \right\}}{f(m+t,n-1)} &\text{ if }\ n>0.\\ \end{array} \right. $$ This is a question about convolution. I can calculate the value of specific $f(m_0,n_0)$ by writing a brute force computer program, but I want to know how to get the explicit expression.

Answer 1

Let $g:\Bbb Z \longrightarrow \Bbb Z$ be such that $g\equiv 0$ except that $g(-1) = g(0) = g(1) = 1$. Then it's easy to verify that for $n>0$ we have

$$f(m, n) = \sum_{j\in\Bbb Z}f(j, n-1) \cdot g(m-j).$$

Let $f_n(m) := f(m,n)$, and observe that $g = f_1$. We can then rewrite for $n>0$

$$f_n(m) = \sum_{j\in\Bbb Z}f_{n-1}(j) \cdot g(m-j) = (f_{n-1}*f_1)(m).$$

Of course, we can further expand and obtain that for $n>0$

$$f_n(m) = (\underbrace{f_1 * f_1 * \dots * f_1}_{n \text{ times}})(m),$$

At this point, one can proceed using the convolution theorem. Do you think you can take it from here?

---

Let $\mathfrak D[f]$ denote the Fourier transform of $f$. The convolution theorem states that

$$\mathfrak D[f*g] = \mathfrak D[f] \cdot \mathfrak D[g].$$

We can couple this with the inverse fourier tranform to turn the problem of calculating $n$ convolutions into the problem of calculating $n$ multiplications.

Indeed, by the theorem we have $\mathfrak D[f_n] = {\left(\mathfrak D[f_1]\right)}^n$. Then, with the inverse fourier transform, we can recover

$$f_n(m) = \frac 1{2\pi}\int_0^{2\pi} \mathfrak D[f_n](\omega)\, e^{i\omega m} \, d\omega = \frac 1{2\pi}\int_0^{2\pi}{\big(\mathfrak D[f_1](\omega)\big)}^n e^{i\omega m} \, d\omega.\tag{1}$$

Now, $\mathfrak D[f_1]$ is a power series of $e^{-i\omega}$, and it's a good exercise to check that, for this kind of function, the integral $(1)$ yields the coefficient of $e^{-i\omega m}$.

With $x = e^{-i\omega}$, we hence have $\mathfrak D[f_1](\omega) = x + 1 + \frac1x,$ and therefore

$$f_n(m) = \left[x^m\right]\left(x + 1 + \frac1x\right)^n. \tag{2}$$

As a side note, you can easily see here the connection with the solution you found. Indeed, we have that $$\begin{align}\left[x^m\right]\left(x + 1 + \frac1x\right)^n &= \left[x^m\right]\left(\frac{x^2 + x + 1}x\right)^n \\&= \left[x^m\right]\left(\frac{\left(x^2 + x + 1\right)^n}{x^n}\right) \\&= \left[x^{m+n}\right]\left(x^2 + x + 1\right)^n \end{align}$$ I do prefer the formulation in $(2)$; I find it better highlights the problem's symmetry about $m=0$.

Now, calculating this is a matter of combinatorics.

In each of the $n$ factors of the product $\left(x + 1 + \frac1x\right)^n$, we must choose one of $x$, $1$ or $1/x$, and the overall product must be $x^m$. Let $a_{-1}$ be the number of $x^{-1}$ we choose, and similarly for $a_0$ and $a_1$. Then, these numbers must satisfy the equations

$$a_{-1}+a_0+a_1 = n \quad\text{ and }\quad a_1 - a_{-1} = m.$$

Subtracting them, we find $a_0 + 2a_{-1} = n - m$, so that $a_0 \equiv n - m \pmod 2$ and $a_0 \leqslant n - m$. Choosing a value for $a_0$ that satisfies these constraints then determines the values of $a_{-1}$ and $a_1$:

$$\begin{align} a_{-1} &= \frac{n-m-a_0}2, \\a_{1} &= \frac{n+m-a_0}2. \end{align}$$

Accounting also for the different orders in which we can choose the factors, we hence have

$$f_n(m) = \sum_{\substack{0\,\leqslant\, t \,\leqslant\, n-m\\t\,\equiv\, n-m\pmod 2}} \frac{n!} {t!{\left(\frac{n+m-t}2\right)}!{\left(\frac{n-m-t}2\right)}!}.$$

You can specialize the formula depending on the parity of $n-m$ to get a 'traditional' index on the summation, but this is the gist of it.