# How to get the formula from its recurrence relation $A(n,m)=A(n-1,m)+A(n-1,m-1)+A(n-2,m)-A(n-2,m-1)$ or its generating function?

1. The recurrence relation of $$A(n,m)$$: $$A(n,m)=A(n-1,m)+A(n-1,m-1)+A(n-2,m)-A(n-2,m-1) \quad\text{for} \quad n\ge2, A(0,0)=0, A(1,0)=1.$$

2. The generating function $$F_n(z)$$: $$F_n(z)=\sum_{m}A(n,m)z^m$$ and form its recurrence relation, we can get $$F_n(z)=(1+z)F_{n-1}(z)+(1-z)F_{n-2}(z),\quad\text{for} \quad n\ge3,F_1(z)=1, F_2(z)=(1+z).$$

QUESTION: In the paper, they get $$A(n,m)=\sum_k\binom{k}{m}\binom{n-1-k}{k-m}$$ and said it is routine to verify. How can we get the formula of $$A(n,m)$$ from its recurrence relation or generating function? By hand or with a computer program?

I have calculated for a long time to get $$A(n,m)$$ but failed. Here is the way I tried. By using Mathematica， $$F_n(z)=-\frac{2^{-n} \left(\left(-\sqrt{z^2-2 z+5}+z+1\right)^n-\left(\sqrt{z^2-2 z+5}+z+1\right)^n\right)}{\sqrt{z^2-2 z+5}}.$$ By doing this way, $$A(n,m)$$ is the coefficient of $$z^m$$ of $$2^{-n+1} \sum_{k=0}^{\infty}(1+z)^{n-2k-1}(5-2 z+z^2)^k.$$ Then $$A(n,m)=\\ \sum_{i=0}^{\infty} \sum _{j=0}^{\infty } \sum _{k=0}^{\infty } 2^{1-n} (-2)^{i+2 j-m} 5^{k-j}\binom{k}{j} \binom{n}{2 k+1} \binom{j}{i+2 j-m} \binom{-2 k+n-1}{i},$$ It's really hard for me to get $$F_n(z)$$'s coefficients of $$z^m$$ from its expression and the result I got is pretty different from the result above.

• "$A(n, m)$ is the coefficient of $x^m$ of [something in which the symbol $x$ does not appear]"
– JBL
Mar 25, 2023 at 13:15
• Have you tried using a two-variable generating function $\sum_{m, n} A(n, m) x^n y^m$? Did that yield anything?
– JBL
Mar 25, 2023 at 13:17
• That was a slip of the pen and I have changed x to z. Thanks for pointing out the error. Besides, I didn't try using the two-variable generating function, I will have a try, thanks for your advice.
– Zero
Mar 25, 2023 at 14:18
• Ok let me know how it goes :)
– JBL
Mar 27, 2023 at 11:41
• Sorry for my late response. I was ill and haven't checked this for quite a long time... It seems like the expression got from the two-variable one is quiet similar to what we want，$$F(n,m)=x/(1-(x+xy+x^2-x^2y)$$, thus $$A(n,m)=\sum _{i=0}^{\infty } \sum _{k=0}^{\infty } \binom{i}{m} \binom{m}{k} (-1)^k \binom{i-m}{n-1-i-k}$$, but I still failed.
– Zero
Apr 5, 2023 at 9:15

You have (correctly) computed the generating function $$F(x, y) = \frac{x}{1 - x - x^2 - xy + x^2y}$$. There are many possible procedures to extract a formula for a coefficient in this series; if you want to end up specifically with the one you quoted, then you can rewrite this as \begin{align*} F(x, y) &= \frac{x}{1 - x} \cdot \frac{1}{1 - \frac{x}{1 - x}(x + y - xy)} \\ & = \frac{x}{1 - x} \sum_k \frac{x^k}{(1 - x)^k}(x + y - xy)^k \\ & = \sum_k (1 - x)^{-k - 1} x^{2k + 1} \left(1 + \frac{y(1 - x)}{x}\right)^k \\ & = \sum_k (1 - x)^{-k - 1} x^{2k + 1} \sum_m \binom{k}{m} \left(\frac{y(1 - x)}{x}\right)^m \\ & = \sum_m y^m \sum_k \binom{k}{m} (1 - x)^{m - k - 1} x^{2k + 1 - m} \\ & = \sum_m y^m \sum_k \binom{k}{m} \sum_N \binom{N+ k - m}{k - m} x^{N + 2k + 1 - m} \\ & = \sum_m y^m \sum_k \binom{k}{m} \sum_n \binom{(n - 2k - 1 + m) + k - m}{k - m} x^{n} \\ & = \sum_m\sum_n x^n y^m \sum_k \binom{k}{m} \binom{n - k - 1 }{k - m}. \end{align*}

(Did I really derive this this way? No, of course I started at the other end and then wrote it upside down. Other paths are undoubtedly possible, and the answer can undoubtedly be written in a plethora of other forms.)

... I have calculated for a long time to get $$A(n,m)$$ but failed. Here is the way I tried. By using Mathematica...

We can solve easily this recurrence by reducing it to a two dimensional equivalent first order recurrence

$$\left( \begin{array}{c} f^1_n \\ f^2_n \\ \end{array} \right) = \left( \begin{array}{cc} 0 & 1 \\ 1-z & z+1 \\ \end{array} \right) \left( \begin{array}{c} f^1_{n-1} \\ f^2_{n-1} \\ \end{array} \right)$$

so determining the eigenvalues we have

$$\left( \begin{array}{cc} 0 & 1 \\ 1-z & z+1 \\ \end{array} \right) = T\Lambda T^{-1}= \left( \begin{array}{cc} \frac{z+\sqrt{(z-2) z+5}+1}{2 (z-1)} & \frac{z-\sqrt{(z-2) z+5}+1}{2 (z-1)} \\ 1 & 1 \\ \end{array} \right) \left( \begin{array}{cc} \frac{1}{2} \left(-\sqrt{z^2-2 z+5}+z+1\right) & 0 \\ 0 & \frac{1}{2} \left(\sqrt{z^2-2 z+5}+z+1\right) \\ \end{array} \right) \left( \begin{array}{cc} \frac{z+\sqrt{(z-2) z+5}+1}{2 (z-1)} & \frac{z-\sqrt{(z-2) z+5}+1}{2 (z-1)} \\ 1 & 1 \\ \end{array} \right)^{-1}$$

$$T^{-1}\left( \begin{array}{c} f^1_n \\ f^2_n \\ \end{array} \right) = \Lambda T^{-1}\left( \begin{array}{c} f^1_{n-1} \\ f^2_{n-1} \\ \end{array} \right)$$