Solve two-variable recursion using generating function

Question

Suppose $T(n,k)$ satisfies the nitial condition $T(0,k)=\delta_{k,1}$ and the recursion $$ T(n,0)=qT(n-1,1),\quad T(n,1)=qT(n-1,2),$$ $$ T(n,k)=qT(n-1,k+1)+pT(n-1,k-1), k>1.$$ Playing around, I think the solution is simple in terms of binomial coefficients.

I write $F(x,y)=\sum_{n,k\ge 0}x^ny^kT(n,k)$ and $$F(x,y)= \sum_{n\ge 0}x^nT(n,0)+\sum_{n\ge 0}x^nyT(n,1)+\sum_{n\ge 0}\sum_{k\ge 2}x^ny^kT(n,k).$$ Using the recursion in the last term I get $$F(x,y)= F(x,0)+\sum_{n\ge 0}x^nyT(n,1)+\sum_{n\ge 0}\sum_{k\ge 2}x^ny^k(qT(n-1,k+1)+pT(n-1,k-1))$$ or $$F(x,y)= F(x,0)+\sum_{n\ge 0}x^nyT(n,1)+xypF(x,y)+q\sum_{n\ge 0}\sum_{k\ge 2}x^ny^kT(n-1,k+1).$$

I am not sure how to proceed from here. There are two terms that I can't relate simply to $F$.

Answer 1

Not a complete solution, but I hope answers your specific question.

The recurrence relations should be used just for $n>0$. Either $T(-1,k)$ is not in the domain at all, or else those values depend on $T(0,k)$ from the initial condition, rather than $T(0,k)$ depending on $T(-1,k)$.

I suspect this one is easier to do one dimension at a time, since the function $S_n(k) = T(n,k)$ (with $n$ fixed and $k$ varying) is entirely determined by the previous function $S_{n-1}(k)$.

So define

$$ G_n(y) = \sum_{k \geq 0} T(n,k) y^k $$

For $n=0$,

$$ G_0(y) = \sum_{k \geq 0} \delta_{k,1} y^k = y $$

For $n>0$, first split for the cases of $k$ just as you did.

$$ G_n(y) = T(n,0) + y T(n,1) + \sum_{k \geq 2} y^k T(n,k) $$ $$ G_n(y) = q T(n-1, 1) + qy T(n-1, 2) + \sum_{k \geq 2} y^k \big( q T(n-1,k+1) + p T(n-1,k-1) \big) $$

All the terms involving $q$ combine nicely to simplify, since the first two are exactly the "missing" terms for $k=0$ and $k=1$ in the next sum.

$$ G_n(y) = q \sum_{k \geq 0} y^k T(n-1,k+1) + p \sum_{k \geq 2} y^k T(n-1,k-1) $$

Next to shift the sum indices - I'll do this carefully since I think it's the core of your question. For the first sum, let $j=k+1$, so $k=j-1$ and $j \geq 1$. Then

$$ \sum_{k \geq 0} y^k T(n-1,k+1) = \sum_{j \geq 1} y^{j-1} T(n-1,j) $$

But since the name of the variable used as a sum index doesn't matter, this equation is the same as

$$ \sum_{k \geq 0} y^k T(n-1,k+1) = \sum_{k \geq 1} y^{k-1} T(n-1,k) $$

For the second sum, use $j=k-1$, $k=j+1$, $j \geq 1$, to get

$$ \sum_{k \geq 2} y^k T(n-1,k-1) = \sum_{j \geq 1} y^{j+1} T(n-1,j) = \sum_{k \geq 1} y^{k+1} T(n-1,k) $$

We can also see that if we expanded these sums into "$+ \cdots +$" notation, we would get exactly the same terms. With practice, one can do these index shifts with a few side scribbles or all in the head, without the temporary other variable name. But there's still the understanding that the variable doesn't mean the same thing on both sides. If we were using a generating function in two variables, we could transform the two variables separately just like this or both at once, as long as we're careful enough with the domain's limiting inequalities.

Back to the full $G_n$ formula,

$$ \begin{align*} G_n(y) &= q \sum_{k \geq 1} y^{k-1} T(n-1,k) + p \sum_{k \geq 1} y^{k+1} T(n-1,k) \tag{1} \label{eq:1} \\ G_n(y) &= \left(py + \frac{q}{y}\right) \sum_{k \geq 1} y^k T(n-1,k) \\ G_n(y) &= \left(py + \frac{q}{y}\right) \big(G_{n-1}(y) - G_{n-1}(0)\big) \end{align*} $$

(This formula is still a formal power series despite the $\frac{1}{y}$, since $G_{n-1}(y) - G_{n-1}(0)$ has no constant term and is a multiple of $y$.)

It's not clear to me what to try next, with no obvious formula or pattern for $G_n(0)$. A dependence of $T(n,k)$ on nearby points in the $(n,k)$ grid is one thing, but a dependence on $T(n-1,0)$ is something else.

Answer 2

This is a complete rewrite of my earlier solution, which was focused on a strategy for guessing an answer. But it transpired in comments that the OP has a conjectural answer (or at least, part of one). And, indeed, starting from the OP's guess, one is inspired to conjecture for $k \geq 1$ that $T(n, k) = 0$ when $n + k$ is even and $$ T(n, k) = p^{(n + k - 1)/2} q^{(n - k + 1)/2} \left( \binom{n}{\frac{n + k - 1}{2}} - \binom{n}{\frac{n + k + 1}{2}}\right) $$ when $n + k$ is odd. Once you've made this conjecture, actually proving it is a simple exercise in induction: for $n = 0$, we have on one hand that $T(0, k) = \delta_{k, 1}$ and on the other hand that $0 = \delta_{k, 1}$ for even $k$ and $p^{(0 + k - 1)/2} q^{(0 - k + 1)/2} \left( \binom{0}{\frac{0 + k - 1}{2}} - \binom{0}{\frac{0 + k + 1}{2}}\right) = \delta_{k, 1}$ for odd positive $k$ (because the only way the binomial coefficient factor can be nonzero is when one of them is $\binom{0}{0}$, and this happens only for $k = \pm 1$). Now fix an integer $N > 1$ and assume (for induction) that the result is valid for $n = N - 1$ and all $k \geq 1$. Then we apply the recursive definition of $T(n, k)$ to compute $T(N, k)$, in several cases:

• If $N + k$ is even then $(N - 1) + (k + 1)$ and $(N - 1) + (k - 1)$ are both even, so $T(N - 1, k + 1) = T(N - 1, k - 1) = 0$ and therefore $T(N, k) = 0$ in this case, as desired.
• If $N$ is even and $k = 1$ then \begin{align*} T(N, 1) & = q \cdot T(N - 1, 2) \\ & = q \cdot p^{(N - 1 + 2 - 1)/2} q^{(N - 1 - 2 + 1)/2} \left( \binom{N - 1}{\frac{N - 1 + 2 - 1}{2}} - \binom{N - 1}{\frac{N - 1 + 2 + 1}{2}}\right) \\ & = p^{(N + 1 - 1)/2} q^{(N - 1 + 1)/2}\left( \binom{N - 1}{\frac{N}{2}} - \binom{N - 1}{\frac{N}{2} + 1}\right). \end{align*} Now for even $N$, $2\binom{N - 1}{N/2} = \binom{N}{N/2}$ and $\binom{N - 1}{N/2} + \binom{N - 1}{N/2 + 1} = \binom{N}{N/2 + 1}$ and therefore $\binom{N - 1}{\frac{N}{2}} - \binom{N - 1}{\frac{N}{2} + 1} = \binom{N}{\frac{N}{2}} - \binom{N}{\frac{N}{2} + 1} = \binom{N}{\frac{N + 1 - 1}{2}} - \binom{N}{\frac{N + 1 + 1}{2}}$. Thus $T(N, 1) = p^{(N + 1 - 1)/2} q^{(N - 1 + 1)/2}\left( \binom{N}{\frac{N + 1 - 1}{2}} - \binom{N}{\frac{N + 1 + 1}{2}}\right)$ in this case, as desired.
• Finally, if $N + k$ is even and $k > 1$ then \begin{align*} T(N, k) &= q \cdot T(N - 1, k + 1) + p \cdot T(N - 1, k - 1) \\ & = q \cdot p^{(N - 1 + k + 1 - 1)/2} q^{(N - 1 - k - 1 + 1)/2} \left( \binom{N - 1}{\frac{N - 1 + k + 1 - 1}{2}} - \binom{N - 1}{\frac{N - 1 + k + 1 + 1}{2}}\right) + p \cdot p^{(N - 1 + k - 1 - 1)/2} q^{(N - 1 - k + 1 + 1)/2} \left( \binom{N - 1}{\frac{N - 1 + k - 1 - 1}{2}} - \binom{N - 1}{\frac{N - 1 + k - 1 + 1}{2}}\right) \\ & = p^{(N + k - 1)/2}q^{(N - k + 1)/2}\left( \binom{N - 1}{\frac{N + k - 1}{2}} + \binom{N - 1}{\frac{N + k - 1}{2} - 1} - \binom{N - 1}{\frac{N + k + 1}{2}} - \binom{N - 1}{\frac{N + k + 1}{2} - 1}\right) \\ & = p^{(N + k - 1)/2}q^{(N - k + 1)/2}\left( \binom{N}{\frac{N + k - 1}{2}} - \binom{N}{\frac{N + k + 1}{2}}\right) \end{align*} in this case, as desired. In all cases we see that the conjecture also holds. Therefore, by induction, the conjecture is valid for all $N, k$ with $k \geq 1$.