# Solve recursion $p[n,m] = p[n-1,m-1] + p[n+1,m-1] + p[n,m-1]$

How to solve the recursion:

$$p[n,m] = p[n-1,m-1] + p[n+1,m-1] + p[n,m-1]$$

Ideally in general, but if you need base cases:

$$p[n,0] = 0 \text{ (for } n \neq 0),$$ $$p[0,0] = 1$$

I've asked a similar question previously and believe $n^{m-2}$ is somehow involved.

Would turning this into a DFQ help?

-
Very similar question: math.stackexchange.com/questions/9548/… – lhf Jun 4 '11 at 1:04

Given your boundary conditions, if we open up the recurrence relation then we discover an $m$-step process, where at each step we change $n$ by $0$ or $\pm 1$. For every walk that ends up at $0$, we "score" one point.

How many such walks exist? There is an equal number $k$ of $+1$s and $-1$s, and so we get

$\displaystyle \sum_{k=0}^{\lfloor m/2 \rfloor} \binom{m}{k,k} = \sum_{k=0}^{\lfloor m/2 \rfloor} \frac{m!}{k!k!(m-2k)!}$

In order to estimate it, let's calculate the largest coefficient, assuming $m$ is divisible by $3$. It is

$\displaystyle \frac{m!}{(m/3)!} \approx \frac{\sqrt{2\pi m}(m/e)^m}{\sqrt{2\pi (m/3)}^3 (m/3e)^m} = \frac{3^m}{(2\pi/3^{1.5})m}$

Roughly, we expect about $O(\sqrt{m})$ of the summands to be of comparable size, so a conjectured upper bound would be $O(3^m/\sqrt{m})$.

-

See OEIS A027907 and references on trinomial coefficients. If you just start making the triangle in a spreadsheet and type the numbers into OEIS you will find it.

-