I am working on a problem that involves a system of recurrence relations with two functions, $A'$ and $A''$. The relations are defined as follows:
$$
\begin{align*}
A'_{n,k,m} &= A'_{n-1,k-1,m} + A''_{n-1,k,m-1}, \\
A''_{n,k,m} &= A'_{n-1,k-1,m-1} + A''_{n-1,k,m}.
\end{align*}
$$
The initial conditions for the system are given by:
$$
A'_{0,0,0} = A''_{0,0,0} = 1,
$$
and it is specified that:
$$
A'_{n,k,m} = A''_{n,k,m} = 0 \quad \text{for any} \quad n < 0, \, k < 0, \, \text{or} \, m < 0.
$$
After attempting to solve this via generating functions without success, I reverted to finding closed forms for $A'_{n,k,m}$ and $A''_{n,k,m}$ for specific values of $m$ and guessed a general solution. The solution depends on whether $m$ is even or odd:
For even $m = 2m'$:
$$
\begin{align*}
A'_{n,k,2m'} &= \binom{n-k-1}{m'-1} \binom{k}{m'}, \\
A''_{n,k,2m'} &= \binom{n-k}{m'} \binom{k-1}{m'-1}.
\end{align*}
$$
For odd $m = 2m' + 1$:
$$
\begin{align*}
A'_{n,k,2m'+1} &= \binom{n-k-1}{m'} \binom{k}{m'}, \\
A''_{n,k,2m'+1} &= \binom{n-k}{m'} \binom{k-1}{m'}.
\end{align*}
$$
Despite having these closed forms, I would like to understand how to derive them systematically using generating functions or other formal methods without resorting to guessing.
I appreciate any insights or references to similar problems. Many thanks in advance!
Best Answer
Let's use $A_{n,k,m}$ and $B_{n,k,m}$.
$$ \begin{cases} A_{n,k,m} = A_{n-1,k-1,m} + B_{n-1,k,m-1}, \\ B_{n,k,m} = A_{n-1,k-1,m-1} + B_{n-1,k,m} \end{cases} $$
If we consider their genfuncs $A(x,y,z)$ and $B(x,y,z)$, the recurrence rewrites into:
$$\begin{cases} A=xyA+xzB+1, \\ B = xyzA+xB+1 \end{cases}$$
Or, in a matrix form:
$$ \begin{pmatrix} 1-xy & xz \\ xyz & 1-x \end{pmatrix} \begin{pmatrix} A \\ B \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \end{pmatrix} $$
This gives the solution:
$$\begin{align} A = \frac{1+xz-x}{1-x^2yz^2-xy+x^2y-x} & & B = \frac{1+xyz-xy}{1-x^2yz^2-xy+x^2y-x} \end{align}$$
Note that there is $z^2$, but not $z$ in the denominator.
It is a strong indicator that the sequence may behave differently on odd and even $m$, so it is indeed wise to, instead of two sequences $A$ and $B$, consider four sequences $A_0,A_1,B_0$ and $B_1$ split by the parity of $m$, so that $A(z) = A_0(z^2)+zA_1(z^2)$ and $B(z) = B_0(z^2)+zB_1(z^2)$.
The sequences in question have the following generating functions:
$$\begin{matrix} A_0 = \frac{1-x}{1-x^2yz-xy+x^2y-x} & A_1 = \frac{x}{1-x^2yz-xy+x^2y-x} \\ B_0=\frac{1-xy}{1-x^2yz-xy+x^2y-x} & B_1 = \frac{xy}{1-x^2yz-xy+x^2y-x} \end{matrix}$$
Since they all are quite similar in nature, let's actually analyze the single sequence with $1$ in the numerator:
$$ F=\frac{1}{1-x^2yz-xy+x^2y-x} $$
By definition, it expands into $$ F=\sum\limits_{s=0}^\infty x^s(1+y-xy+xyz)^s $$ Let's now try to find its coefficient near $x^n y^k z^m$:
$$\begin{align} [x^n y^k z^m] F &= [x^{n} y^k z^m]\sum\limits_{s} x^s(1+y(1-x+xz))^s\\ &=[x^{n} z^m]\sum\limits_{s} \binom{s}{k}x^s((1-x)+xz)^k \\ &= \binom{k}{m}[x^{n-m}](1-x)^{k-m}\sum\limits_{s} \binom{s}{k}x^s. \end{align}$$
Note that $\sum\limits_s \binom{s}{k} x^s = \frac{x^k}{(1-x)^{k+1}}$ is a standard generating function, thus we get
$$ =\binom{k}{m} [x^{n-m}]\frac{x^k(1-x)^{k-m}}{(1-x)^{k+1}}=\binom{k}{m} [x^{n-k}]\frac{x^m}{(1-x)^{m+1}} $$
Using the same substitution again, we finally get
$$ \boxed{[x^n y^k z^m] F(x,y,z) =\binom{k}{m} \binom{n-k}{m}} $$
Specific formulas for $A_0,A_1,B_0$ and $B_1$ trivially follow from this.