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?



Do you recognize this sequence of polynomials?
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](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.376.3755&rep=rep1&type=pdf), 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](https://sagecell.sagemath.org/?z=eJxdizkOgDAMwHZekY2kTQVl5ytIsDWhAZXj_ZQRRlu2sLHCCPdcsJUXWmr2kuzE48qIIdKE4pXAwZJsy2lecXDG9jPK36Y-LKG6DtC8-kgMytAzCNEDAbMhMw==&lang=sage&interacts=eJyLjgUAARUAuQ==).


#### 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](https://sagecell.sagemath.org/?z=eJxVizsSgCAMBXtPkY6AyTjQexVnsCNIdPBzfkUru7c7-4QyKYxwxYpGGhjbdVtNeuB-FkT2dkLpvQUHc9K1pLhgcEryM8rSP2cWzs23goN7f8NHbRMIgSfQp7I3VNogng==&lang=sage&interacts=eJyLjgUAARUAuQ==) for one of the sums.


