Powers of $2$ up to $2^{m-1}$ from a polynomial of degree $m-1$

Question

Let $T(n,k)$ be a triangle of coefficients such that $T(n,k)\geqslant0$ for $n>0$, $0<k\leqslant n$, $0$ otherwise. Also $$T(2n+1,1)=\frac{1}{2n+1}, T(2n,1)=0$$ $$T(n,k)=\frac{1}{n}(T(n-1,k-1)+(n-2)(T(n-2,k)+\frac{T(n-2,k-1)}{n-1}))$$ Let $$P(n,m)=m\sum\limits_{k=1}^{m}n^{k-1}T(m,k)(-1)^{m+k}$$ I conjecture that $$P(n,m)=2^{n-1}, 0<n\leqslant m$$ To verify it one may use this pari prog:

T(n)=my(v, v1, v2); v=vector(n, i, 0); v[1]=1; v1=v; if(n>1, v[1]=0; v[2]=1/2); v2=v; for(i=3, n, v[1]=if(i%2,1/i); for(j=2, i, v[j]=(v2[j-1]+(i-2)*(v1[j]+v1[j-1]/(i-1)))/i); v1=v2; v2=v); v
P(n, m)=my(A=T(m)); m*sum(k=1, m, n^(k-1)*A[k]*(-1)^(m+k))

Is there a way to prove it?

Answer 1

This is a fun problem! You start out by describing the conjectured coefficients of $P(n,m)$, but presumably you started out by computing the polynomial which interpolates $2^{n-1}$ and then noticed a pattern in the coefficients. So I'll start in that order: Let $Q(n,m)$ be the unique degree $m-1$ polynomial in $n$ which obeys $$Q(n,m) = 2^{n-1} \ \text{for} \ 0 < n \leq m.$$ For any $n>0$, we know that $2^{n-1}$ is the sum of the $(n-1)$-st row of Pascal's triangle: $$2^{n-1} = \sum_{k=0}^{n-1} \binom{n-1}{k} =\sum_{k=0}^{n-1} \frac{(n-1)(n-2) \cdots (n-k)}{k!}.$$ If $n \leq m$, then the terms with $k \geq m$ are zero, so we have $$2^{n-1} = \sum_{k=0}^{m-1} \frac{(n-1)(n-2) \cdots (n-k)}{k!} \quad 0 < n \leq m. \quad (\ast)$$ The right hand side of $(\ast)$ is clearly a polynomial in $n$ of degree $m-1$, so it is $Q(n,m)$. I'm going to switch the variable $n$ to $x$ for clarity. So $$Q(x,m) = \sum_{k=0}^{m-1} \frac{(x-1)(x-2) \cdots (x-k)}{k!}.$$ So $$Q(x,m) - Q(x,m-1) = \frac{(x-1)(x-2) \cdots (x-m+1)}{(m-1)!}$$ and $$Q(x,m) - Q(x,m-1) = \frac{x-m+1}{m-1} \left( Q(x,m-1) - Q(x,m-2) \right). \quad (\dagger)$$

Now, put $$Q(x,m) = \sum_{k=0}^{m-1} U(m,k) x^k.$$ Comparing the coefficient of $x^{\ell}$ on both sides of $(\dagger)$, we get $$U(m,\ell) - U(m-1, \ell) = $$ $$\frac{1}{m-1} \left( U(m-1, \ell-1) - U(m-2, \ell-1) \right) - \left( U(m-1, \ell) - U(m-2, \ell) \right).$$ Presumably, it shouldn't be hard to rearrange this into your recurrence; I'm going to stop here.