Triangular Array's Recursive Formula Breakdown

Question

I have the following polynomials: $$1$$ $$z-1$$ $$z^2-2z+3$$ $$z^3-3z^2+9z-15$$ $$z^4-4z^3+18z^2-60z+93$$ $$z^5-5z^4+30z^3-150z^2+465z-725$$ $$...$$ They are generated both recursively and explicitly. The recursive formula is $$p_n(z)=z^n-\sum_{k=0}^{n-1}\binom{n}{k}\frac{1+(-1)^{n-k}+2(n-k)(-1)^{n-k-1}}{2}p_k(z)$$ Placing the unsigned coefficients in a lower triangular array, $$ \begin{matrix} 1\\ 1&1\\ 1&2&3\\ 1&3&9&15\\ 1&4&18&60&93\\ 1&5&30&150&465&725 \end{matrix} $$ If we call the first row and column the 0-th row and column, then the columns 0 through 3 satisfy the following recurrence relation: If $T(n,k)$ is the entry in the nth row and kth column, then $$T(n,k)=(2k-1)T(n-1,k-1)+T(n-1,k)$$ where $T(n,k)=0$ if $n<k$, and the explicit formula $$T(n,k)=\binom{n}{k}(2k-1)!!$$ What would make an obvious pattern in the triangle break down after the 3rd column? If it were to continue, then $T(4,4)=7T(3,3)=105$, but instead we have 93. I know there are many sequences that mimic others very early and diverge from the desired results, but I'm trying to identify in the recursive formula the terms that would be responsible for this. Any thoughts?

Answer 1

$$p_n(z)=z^n-\sum_{k=0}^{n-1}\binom{n}{k}\frac{1+(-1)^{n-k}+2(n-k)(-1)^{n-k-1}}{2}p_k(z)$$

$T(n, k) = [z^{n-k}]p_n(z)$ and you're particularly interested in $T(n, n) = [z^0]p_n(z)$

$$T(n, n) = [n = 0] - \sum_{k=0}^{n-1}\binom{n}{k}\frac{1+(-1)^{n-k}+2(n-k)(-1)^{n-k-1}}{2}T(k, k)$$

• $T(0, 0) = 1$ is a special case.
• $T(1, 1) = -\binom{1}{0}T(0, 0) = -1$
• $T(2, 2) = -\left(-\binom{2}{0}T(0,0) + \binom{2}{1}T(1,1)\right) = -(-1-2) = 3$
• $T(3, 3) = -\left( 3\binom{3}{0}T(0, 0) - \binom{3}{1}T(1, 1) + \binom{3}{2}T(2, 2) \right) = -(3 + 3 + 9) = -15$
• $T(4, 4) = -\left( -3\binom{4}{0}T(0, 0) + 3\binom{4}{1}T(1, 1) - \binom{4}{2}T(2, 2) + \binom{4}{3}T(3, 3) \right) = -(-3 - 12 - 18 - 60) = 93$

So basically the coincidence with the odd factorial seems to be nothing more than an coincidence. $T(2, 2) = \binom{2}{0} + \binom{2}{1}$ just happens to be $3!!$. In $T(3, 3)$, the factors of 3 in $3\binom{3}{0}$ and $\binom{3}{1}$ come from different places. In general the coefficient of $-T(n-1, n-1)$ in the sum that makes up $T(n, n)$ is $\binom{n}{n-1} = n$, but there's no reason for the remaining terms to sum to $-(n-1)T(n-1, n-1)$.

Answer 2

This is a really interesting problem! I have only looked at it for a few minutes, so I haven't proved anything, but looking at your triangle array I spotted something interesting: there is a very striking resemblance to Pascal's Triangle!!!

If you go by columns, starting with the second column:

$1, 2, 3, 4, 5, \cdots$ are all divisible by $1$ and are equal to the second column in Pascal's Triangle. ($nC1$)

$3, 9, 18, 30, \cdots$ are all divisible by the first number, $3$, and are equal to $3$ times the third column in Pascal's Triangle. ($nC2$)

$15, 60, 150, \cdots$ are all divisible by the first number, $15$, and are equal to $15$ times the fourth column in Pascal's Triangle. ($nC3$)

etc.

However, I can't figure out yet what the first number in each column sequence is ($1, 3, 15, \cdots$); I'll get back to you later if I figure it out.

Enjoy!