Recursion for the Chebyshev transform of $m^n$

Question

• Let

$$ R(n, q, m) = R(n-1, q+1, m) + \sum\limits_{j=0}^{q} (-1)^{q-j}R(n-1, j, m), \\ R(0, q, m) = (m-1)^q $$

I conjecture that $R(n, 0, m)$ is a Chebyshev transform of $m^n$.

Examples of Chebyshev transform:

• A090412 - $2^n$
• A090413 - $3^n$

Here is the PARI/GP program to compute $R(n, 0, m)$:

R_upto(n, m) = my(v1, v2, v3); v1 = vector(n + 1, i, (m-1)^(i-1)); v2 = v1; v3 = vector(n + 1, i, 0); v3[1] = 1; for(i = 1, n, for(q = 0, n - i, v2[q + 1] = v1[q + 2] + sum(j = 0, q, (-1)^(q-j)*v1[j + 1])); v1 = v2; v3[i + 1] = v1[1]); v3

Is there a way to prove it?

Answer 1

UPDATED. The argument below is corrected.

Apparently, under Chebyshev transform of a generating function $A(x)$ OP understands a function $B(x) := C(-x^2)A(xC(-x^2))$, where $C(x):=\frac{1-\sqrt{1-4x}}{2x}$ is the generating function for Catalan numbers.

Let $m$ be fixed.

Consider the generating function $$\mathcal{R}(x,y):=\sum_{n=0}^\infty\sum_{j=0}^\infty R(n,j,m)x^jy^n$$ and so $\mathcal{R}(x,0) = f(x)$ is given.

Then the recurrence formula for $R(n,q,m)$ translates into $$(\star)\quad\mathcal{R}(x,y)-\mathcal{R}(x,0) = \frac{y}x(\mathcal{R}(x,y)-\mathcal{R}(0,y)) + \frac{y}{1+x}\mathcal{R}(x,y),$$ from where we need to deduce the value of $g(y) := \mathcal{R}(0,y)$. Expressing $\mathcal{R}(x,y)$ in the last equation, we get $$\mathcal{R}(x,y) = \frac{1+x}{x+x^2-(1+2x)y}\big(xf(x)-yg(y)\big).$$ Here the series $xf(x)-yg(y)$ must be divisible by the polynomial $x+x^2-(1+2x)y$. Plugging in its zero $\frac{\sqrt{1+4y^2}-1+2y}2=C(-y^2)y^2+y$, we get $$g(y) = (C(-y^2)y+1)f\big(C(-y^2)y^2+y\big).$$

---

Plugging $f(x) = (1-(m-1)x)^{-1}$ in the general solution, we get $$g(y) = (C(-y^2)y+1)\frac1{1-(m-1)(C(-y^2)y^2+y)}.$$ To show that it is the same as required $\frac{C(-y^2)}{1-myC(-y^2)}$, compute their difference: $$g(y) - \frac{C(-y^2)}{1-myC(-y^2)} = \frac{1-C(-y^2)-C(-y^2)^2y^2}{(1-(m-1)(C(-y^2)y^2+y))(1-myC(-y^2))},$$ which is zero since $1-C(-y^2)-C(-y^2)^2y^2=0$ as follows from the definition of $C$.