2

For a positive integer $m$ and a non-negative integer $n$, find $A_{m,n}$ which satisfies the following :

  1. For every $n$, $A_{1,n} = 1$

  2. If $n>0$, then $A_{m,n}$ = $\displaystyle \sum_{i=0}^{m-1}A_{m-i,n+i-1}$

  3. $A_{m,0} = A_{m-1,0}+\displaystyle \sum_{i=0}^{m-2}A_{m-i-1,i}$

  • I found out that $A_{m,n} = A_{m-1,n+1} + A_{m,n-1}$
Phicar
  • 14,722
19017김범준
  • 123

1 Answers1

1

The closed form turns out to be $$\color{blue}{A_{m,n}=\frac{n+2}{n+2m}\binom{n+2m}{m-1}.}\tag{*}\label{results}$$

Observe that, using "2.", we can write "3." as $A_{m,0}=A_{m-1,0}+A_{m-1,1}$ (for $m>1$).

Now we use generating functions. Let $A_n(x)=\sum_{m>0} A_{m,n}x^{m-1}$. Then $$A_0(x)=1+\sum_{m>1}(A_{m-1,0}+A_{m-1,1})x^{m-1}=1+x\big(A_0(x)+A_1(x)\big)\tag{1}\label{initial}$$ and, similarly, for $n>0$ $$A_n(x)=1+\sum_{m>1}(A_{m,n-1}+A_{m-1,n+1})x^{m-1}=1+\big(A_{n-1}(x)-1\big)+x A_{n+1}(x).$$

Thus, $xA_{n+1}(x)-A_n(x)+A_{n-1}(x)=0$, which is a linear recurrence, solved by $$A_n(x)=A_+(x)\left(\frac{1+\sqrt{1-4x}}{2x}\right)^n+A_-(x)\left(\frac{1-\sqrt{1-4x}}{2x}\right)^n,\tag{2}\label{general}$$ where $A_+$ and $A_-$ are some functions of $x$ representable by power series since $A_0$ and $A_1$ are. And since $A_n$ is a power series (as well) for each $n$, we must have $A_+=0$ identically. Hence $A_-=A_0$. Now \eqref{general} at $n=1$ gives $A_1$ in terms of $A_0$, which we put it into \eqref{initial}. This gives $A_0$, and \eqref{general} now reads $$A_n(x)=\left(\frac{1-\sqrt{1-4x}}{2x}\right)^{n+2},$$ which has a known expansion (see also this article for even more general setting) $$A_n(x)=\sum_{k\geqslant 0}\binom{2k+n+2}{k}\frac{n+2}{2k+n+2}x^k.$$

"Renaming" the summation index (according to $k=m-1$), we get the expected \eqref{results}.

metamorphy
  • 39,111