Do you recognize this sequence of polynomials?

Question

In teaching my linear algebra students about Gram-Schmidt orthogonalization, I found a curious sequence of polynomials. They are closely related to Legendre polynomials, but they also appear to be related to Catalan numbers. (Several of the statements below are conjectural and I am not an expert on orthogonal polynomials, so please bear with me.)

Recall that if we apply the Gram-Schmidt process to the sequence $\{1,t,t^2,t^3,...\}$, where the inner product is given by $\left<f,g\right>=\int_{-1}^1 f(t)g(t)dt$, then one obtains a the Legendre polynomials.

Doing Gram-Schmidt for the first time is always a pain, and I wanted to make the problem easier to do by hand by choosing the initial basis in such a way to avoid a lot of uncomfortable fractions. I gave my students the set $\{1,2t,6t^2,20t^3\}$ and told them to use the inner product $\left<f,g\right>=\int_{0}^1 f(t)g(t)dt$. (This yields a sort of "shifted" version of the Legendre polynomials.) Notice that the coefficients of these monomials are the "central" binomial coefficients $\frac{(2n)!}{n!^2}$. If we apply Gram-Schmidt to these, then we get the polynomials $\{1,2t-1,6t^2-6t+1,20t^3-30t^2+12t-1\}$. (In spite of my efforts, one of my students declared that, upon finding these, he could no longer feel joy.)

The new polynomials that I want to know about are obtained by writing these "shifted" Legendre polynomials as linear combinations of the initial polynomials. Thus, in this instance, we have $$\left[\begin{array}{c} 1 \\ t-1 \\ 6t^2-6t+1 \\ 20t^3-30t^2+12t-1 \\ \end{array}\right] =\left[\begin{array}{cccc} 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 1 & -3 & 1 & 0 \\ -1 & 6 & -5 & 1 \\ \end{array}\right] \left[\begin{array}{c} 1 \\ 2t \\ 6t^2 \\ 20t^3 \\ \end{array}\right].$$ We use the coefficient matrix here to define a new sequence by $$\left[\begin{array}{c} f_0 \\ f_1 \\ f_2 \\ f_3 \\ \end{array}\right] =\left[\begin{array}{cccc} 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 1 & -3 & 1 & 0 \\ -1 & 6 & -5 & 1 \\ \end{array}\right] \left[\begin{array}{c} 1 \\ t \\ t^2 \\ t^3 \\ \end{array}\right] =\left[\begin{array}{c} 1 \\ t-1 \\ t^2-3t+1 \\ t^3-5t^2+6t-1 \\ \end{array}\right].$$ I hope that the reader now understands how to define $f_n$ for all $n$. Use the coefficients that are required to write the orthogonal polynomials with respect to the monomials $\frac{(2n)!}{n!^2}t^n$.

My first thought about these was that they should also be a sequence of orthogonal polynomials. They seem to have the root-interlacing property, although the roots appear to be unbounded. This makes me think that they are related to Laguerre polynomials. (The roots of the Legendre polynomials are necessarily between -1 and 1.) Also, these polynomials seem to obey the (very nice) 3-term recurrence $tf_n=f_{n-1}+2f_n+f_{n+1}$ for $n=1,2,3,4,....$

This is where the Catalan numbers seem to appear. Recall that the $n$th Catalan number is $C_n=\frac{(2n)!}{n!(n+1)!}.$ If we had an inner product on the space of polynomials such that $\left<t^i,t^j\right>=C_{i+j}$, then applying the Gram-Schmidt process to the sequence $\{1,t,t^2,t^3,t^4,...\}$ appears to yield the sequence $f_n$. Is there a function $g$ such that $\int_0^\infty t^n g(t)dt=C_n$? I am guessing that such $g$ should be defined on $[0,\infty)$ because of the behavior of the roots of $f_n$.

What are these polynomials called?

Answer 1

Let $b_n(t)$ be the Morgan-Voyce polynomial defined by $$\begin{eqnarray}b_0(t) &=& 1 \\ b_1(t) &=& t + 1 \\ b_n(t) &=& (t+2) b_{n-1}(t) - b_{n-2}(t) \end{eqnarray}$$

Then $f_n(t) = (-1)^n b_n(-t)$ fits your recurrence.

See Rising diagonal polynomials associated with Morgan-Voyce polynomials, Swamy, M. N., Fibonacci Quarterly 38.1 (2000) pp61-69 for an overview of these polynomials which includes the following observations:

• $b_n(t) = \sum_{k=0}^n \binom{n+k}{n-k} t^k$ (2.10)
• The zeros of $b_n(t)$ are $-4 \sin^2 \left(\frac{2r-1}{2n+1} \frac{\pi}2 \right)$ for $r = 1, 2, \ldots, n$ (2.14)
• $b_n(t)$ is orthogonal over $(-4,0)$ with respect to the weight function $\sqrt{-(t+4)/t}$ (2.26)

---

In light of that the following is largely superfluous, but...

From $b_n(t) = \sum_{k=0}^n \binom{n+k}{n-k} t^k$ we can test that we get the original "shifted" Legendre polynomials, and since each transformation in the process which gives $f_n$ is invertible that would validate the conjectured identity of the $f_n$. Denote the polynomials which come from the Gram-Schmidt process as $u_n$, so $$u_n(t) = \binom{2n}{n}t^n - \sum_{j=0}^{n-1} \frac{\left<u_j,\binom{2n}{n}t^n\right>}{\left<u_j,u_j\right>} u_j(t)$$

Then the conjecture is that $$\begin{eqnarray*}u_n(t) \stackrel?= \tilde{f_n}(t) &:=& \sum_{k=0}^n \binom{2k}{k} t^k [t^k] f_n(t) \\ %&=& (-1)^n \sum_{k=0}^n \binom{2k}{k} t^k [t^k] b_n(-t) \\ &=& \sum_{k=0}^n (-1)^{n+k} \binom{2k}{k} \binom{n+k}{n-k} t^k \\ \end{eqnarray*}$$

Product with original basis function

$$\begin{eqnarray*} \left<\tilde{f_j}, \binom{2n}{n}t^n\right> &=& \int_0^1 \tilde{f_j} \binom{2n}{n}t^n dt \\ &=& \binom{2n}{n} \int_0^1 \sum_{k=0}^j (-1)^{j+k} \binom{2k}{k} \binom{j+k}{j-k} t^{k+n} dt \\ &=& \binom{2n}{n} \sum_{k=0}^j \frac{(-1)^{j+k}}{k+n+1} \binom{2k}{k} \binom{j+k}{j-k} \\ &=& \frac{1}{n+j+1} \binom{2n}{n-j} \end{eqnarray*}$$

with some help from Sage.

Self-product

$$\begin{eqnarray*} \left<\tilde{f_j}, \tilde{f_j}\right> &=& \int_0^1 \tilde{f_j}^2 dt \\ &=& \int_0^1 \tilde{f_j} \sum_{k=0}^j (-1)^{j+k} \binom{2k}{k} \binom{j+k}{j-k} t^k dt \\ &=& \sum_{k=0}^j (-1)^{j+k} \binom{j+k}{j-k} \int_0^1 \tilde{f_j} \binom{2k}{k} t^k dt \\ &=& \sum_{k=0}^j (-1)^{j+k} \binom{j+k}{j-k} \frac{1}{k+j+1} \binom{2k}{k-j} \end{eqnarray*}$$ and the term in the sum has support only when $j=k$, yielding $$\left<\tilde{f_j}, \tilde{f_j}\right> = \frac{1}{2j+1}$$

Gram-Schmidt induction

If we assume that $u_j = \tilde{f_j}$ for all $j < n$ then

$$\begin{eqnarray*} u_n(t) &=& \binom{2n}{n}t^n - \sum_{j=0}^{n-1} \frac{\left<\tilde{f_j},\binom{2n}{n}t^n\right>}{\left<\tilde{f_j},\tilde{f_j}\right>} \tilde{f_j}(t) \\ &=& \binom{2n}{n}t^n - \sum_{j=0}^{n-1} \frac{2j+1}{n+j+1} \binom{2n}{n-j} \tilde{f_j}(t) \\ &=& \binom{2n}{n}t^n - \sum_{j=0}^{n-1} \frac{2j+1}{n+j+1} \binom{2n}{n-j} \sum_{k=0}^j (-1)^{j+k} \binom{2k}{k} \binom{j+k}{j-k} t^k \\ &=& \binom{2n}{n}t^n + \sum_{k=0}^{n-1} (-1)^k \binom{2k}{k} t^k \sum_{j=k}^{n-1} (-1)^{j+1} \frac{2j+1}{n+j+1} \binom{2n}{n-j} \binom{j+k}{j-k} \\ % subst j: = n-j &=& \binom{2n}{n}t^n + \sum_{k=0}^{n-1} (-1)^{n+k} \binom{2k}{k} t^k \sum_{j=1}^{n-k} (-1)^{j+1} \frac{2n-2j+1}{2n-j+1} \binom{2n}{j} \binom{n-j+k}{n-j-k} \\ &=& \binom{2n}{n}t^n + \sum_{k=0}^{n-1} (-1)^{n+k} \binom{2k}{k} t^k \binom{n+k}{n-k} \\ &=& \sum_{k=0}^n (-1)^{n+k} \binom{2k}{k} \binom{n+k}{n-k} t^k \end{eqnarray*}$$

with some more help from Sage for one of the sums.

Answer 2

The recurrence $f_{n+1} = (t-2)f_n - f_{n-1}$ with $f_0=1$ and $f_1=t-1$ suggests that $f_n$ can be expressed in terms of Chebyshev polynomials as: \begin{split} f_n(t) &= T_n(\tfrac{t}2-1) + \frac{t}{2} U_{n-1}(\tfrac{t}2-1) \\ &=U_n(\tfrac{t}2-1) + U_{n-1}(\tfrac{t}2-1), \end{split} and so their orthogonality and other properties should follow from those of Chebyshev polynomials.

Answer 3

See OEIS A129818 and the unsigned version A085478 as well as A049310, A011973, and A054142.

Relations among the Gegenbauer, Jacobi, Legendre, and the polynomials highlighted in this post can be found in OEIS A097610 via A011973 and A049310.

A102426, A030528, A011973, A049310 contain relations to the Pascal, Fibonacci, Chebyshev, and other polynomials.