# Finding a recursion for a sum of Legendre polynomials

The polynomial

$a_n(x):=P_n(x)-\frac{n-1}{n}P_{n-2}(x)$

where $P_n(x)$ is a Legendre polynomial came up while I was investigating methods for estimating the error in Gaussian quadrature.

I am wondering if a recursion relation (homogeneous/inhomogeneous, three terms or more) might be found for the $a_n(x)$. Of course I can obviously just generate them directly after performing the recursion for Legendre polynomials, but I'm wondering if there might be a way to generate this sequence of polynomials from the first few members, for instance $a_1(x)=x$ and $a_{2}(x)=\frac{3}{2}x^2-1$...

I have heard of Sister Celine's method; my understanding of it however is that one must first have a representation for your polynomials of interest in terms of a hypergeometric function. So an alternative question might be: can $a_n(x)$ be represented as a single hypergeometric function, most probably with one of the numerator parameters being -n?

-
I tried solving this by direct calculation and got screwed up by the negative sign in your formula for a_n. Is it possible there is a mistake and the correct expression is: a_n = P_n + (n - 2) / n P_{n-2} –  Mikola Aug 20 '10 at 18:30
I had a similar thought too (things would seriously simplify with that plus sign). –  darij grinberg Aug 20 '10 at 18:39
Darij and Mikola: No, it's correct; the useful property for me here in considering $a_{n}(x)$ is that the roots of $P_n(x)$ and $a_{n+1}(x)$ interlace. (remember where I said these polynomials came from?) :) And yes, I know why you want it very badly to be a plus sign, but alas, this is what cropped up. –  J. M. Aug 20 '10 at 22:32

There is a general tactics for this. Recall that the three-term recurrence for the Legendre polynomials comes from a differential equation for their generating function.

The general background:

Generally, if a power series $f=\sum\limits_{i=0}^{\infty} p_it^i$ (where the coefficients $p_i$ belong to some field $K$ (for example, we can have $K=\mathbb Q$ or $K=\mathbb C\left(x\right)$ or whatever)) satisfies a differential equation $\sum\limits_{k=0}^n a_kf^{(k)}=0$ with coefficients $a_k\in K\left[t\right]$ (that's right, they can be polynomials in $t$), then we get a recurrence equation for the coefficients $p_i$ of $f$ in the following way:

Since $f=\sum\limits_{i=0}^{\infty} p_it^i$, we have $f^{(k)}=\sum\limits_{i=0}^{\infty} \left(i+k\right)\left(i+k-1\right)...\left(i+1\right)p_{i+k}t^i$. Hence, the equation $\sum\limits_{k=0}^n a_kf^{(k)}=0$ becomes $\sum\limits_{k=0}^n a_k\sum\limits_{i=0}^{\infty} \left(i+k\right)\left(i+k-1\right)...\left(i+1\right)p_{i+k}t^i=0$. Now write each $a_k$ as a polynomial in $t$, and expand the product on the left hand side. You get an equation of the form $\sum\limits_{u=0}^{\infty}\left(\text{some }K\text{-linear combination of }p_{u-m},p_{u-m+1},...,p_{u+n}\right)t^u=0$, where $m$ is $\max\left\lbrace\deg a_0,\deg a_1,...,\deg a_n\right\rbrace$. Now, equating coefficients, we get a recurrence equation for the $p_i$. Sometimes it may "degenerate", i. e. for some $i$ the coefficient before $p_i$ may be zero, but this shouldn't happen too often.

[Note that this recurrence equation has finitely many terms, since $a_k$ are polynomials in $t$. Had we allowed $a_k$ to be arbitrary power series in $t$, we would have obtained an infinite recurrence.]

Applications to the question:

The generating function for the Legendre polynomials is $\dfrac{1}{\sqrt{1-2xt+t^2}}$; this means that $\dfrac{1}{\sqrt{1-2xt+t^2}}=\sum\limits_{n=0}^{\infty}P_nt^n$ as a power series in the indeterminate $t$ over $K=\mathbb Q\left[x\right]$, where I write $P_n$ for $P_n\left(x\right)$.

Now you are interested in finding a recurrence relation for the $na_n=nP_n-\left(n-1\right)P_{n-2}$ (here I have multiplied by $n$ to get rid of the ugly fraction). So you are looking for a differential equation - with coefficients that are polynomial in $t$ and rational in $x$ - that the power series $\sum\limits_{n=0}^{\infty}na_nt^n$ satisfies.

Note that

$\sum\limits_{n=0}^{\infty}na_nt^n=\sum\limits_{n=0}^{\infty}\left(nP_n-\left(n-1\right)P_{n-2}\right)t^n=\sum\limits_{n=0}^{\infty}nP_nt^n-\sum\limits_{n=0}^{\infty}\left(n-2\right)P_{n-2}t^n-\sum\limits_{n=0}^{\infty}P_{n-2}t^n$ $=tU^{\prime}-t^3U^{\prime}-t^2U$,

where $U$ denotes the power series $\dfrac{1}{\sqrt{1-2xt+t^2}}=\sum\limits_{n=0}^{\infty}P_nt^n$.

Computations best left to a CAS now yield $\sum\limits_{n=0}^{\infty}na_nt^n=\dfrac{t\left(xt^2+x-2t\right)}{\sqrt{t^2-2tx+1}^3}$. This is the function we wish to find a differential equation for. Now there is a general way for it: If $P$ and $Q$ are two polynomials in $x$ and $t$, then the function $V:=\frac{P}{\sqrt Q}$ satisfies the differential equation $PQ\dfrac{d}{dt}V=\left(P^{\prime}Q - \dfrac{PQ^{\prime}}2\right)V$. This hopefully makes a "nice" recurrence. (In your case $P=t\left(xt^2+x-2t\right)$ and $Q=\left(t^2-2tx+1\right)^3$.)

-
Nice approach! You started your post with the assertion that the three-term recurrence relation comes from the differential equation for the generating function. Could you please expand on that, briefly, or point me to a (preferably digital) reference? The only proof that I know to establish a recurrence relation is to use the fact that $P_{n+1} - a_{n+1}xP_n = c_0P_0 + \cdots + c_nP_n$ for some appropriate constants $a_{n+1} and $c_0,..., $c_n$ and then to apply orthogonality. –  Jerry Gagelman Aug 21 '10 at 16:22
Jerry: One merely shows that the generating function $G(x,w)=\left(1-2xw+w^2\right)^{-1/2}$ satisfies the PDE $\left(1-2xw+w^2\right)\frac{\partial G}{\partial w}=(x-w)G$, and then replaces the generating function with its series expansion and then comparing coefficients. –  J. M. Aug 21 '10 at 16:38
P.S. Chihara's "An Introduction to Orthogonal Polynomials" would make an excellent starting point. –  J. M. Aug 21 '10 at 16:41
I have edited my post. –  darij grinberg Aug 21 '10 at 16:41

(this is a variation on Darij's answer)

Note that "holonomic" generating functions $f(x)$, i.e. generating functions satisfying a linear differential equation with polynomial coefficients (in $x$) enjoy rich closure properties.
For a (very brief) summary, see Table 1 of a paper on guessing (sorry, I couldn't find a better reference, but there should be one...). Moreover, all these closure properties can be made "effective": if we know the order and the degree of the coefficients of the diffential equation for $f(x)$ and for $g(x)$, we can (easily) compute bounds for order and coefficient degree of the differential equation for $f+g$, $f\cdot g$, etc.

Moreover, it turns out that the (Taylor) coefficient sequence of a holonomic generating function satisfies a linear recurrence with polynomial coefficients, i.e., is P-recursive, and the P-recursive sequences are precisely the coefficient sequences of holonomic generating functions.

Thus, to find such a recurrence (or differential equation), it is often easiest to use gfun for Maple by Bruno Salvy and Paul Zimmermann, or the Mathematica equivalent by Mallinger (I think). Unfortunately, the FriCAS package described in 1 only does the guessing part, i.e., you would need to compute the bounds yourself and then check. In the case at hand the results are below.

However, you also asked, whether the solution is hypergeometric. To check this, you simply feed the recurrence you found below into Petkovsek's program Hyper, it will tell you whether there is a hypergeometric solution. (most probably no, because if the degree of the coefficient polynomials of the hypergeometric solution are not huge, guessPRec and guessHolo would have found it.)

In case you are dealing with orthogonal polynomials, the Askey Wilson scheme by Koekoek and Swarttouw is a great reference to find the basic information.

(1) -> guessHolo(cons(x, [(legendreP(n, x)-(1-1/n)*legendreP(n-2, x)) for n in 2..30]), variableName==t)

(1)
[
[
n
[t ]f(t):
4     2  2     5     3           4     2  ,,
((- 2t  - 2t )x  + (t  + 6t  + t)x - 2t  - 2t )f  (t)

+
3       2      4      2           3       ,
((- 3t  - 7t)x  + (3t  + 15t  + 2)x - 8t  - 2t)f (t)

+
2      2     3            2
((t  - 3)x  + (t  + 3t)x - 4t  + 2)f(t)
=
0
,
2           2 3      2       3 4      3 2     3
3t x  - 2t   15t x  - 13t x   35t x  - 39t x  + 6t       4
f(t)= x + ---------- + -------------- + --------------------- + O(t )]
2              6                   8
]
Type: List(Expression(Integer))
(2) -> guessPRec cons(x, [(legendreP(n, x)-(1-1/n)*legendreP(n-2, x)) for n in 2..30])

(2)
[
[
f(n):
4      3      2             2     4      3      2
((4n  + 28n  + 67n  + 63n + 18)x  - 4n  - 28n  - 68n  - 68n - 24)
*
f(n + 2)
+
4      3       2              3
(- 8n  - 52n  - 118n  - 107n - 30)x
+
4      3       2
(8n  + 52n  + 120n  + 114n + 36)x
*
f(n + 1)
+
4      3      2             2     4      3      2
((4n  + 24n  + 51n  + 46n + 15)x  - 4n  - 24n  - 52n  - 48n - 16)f(n)
=
0
,
2
3x  - 2
f(0)= x, f(1)= -------]
2
]
Type: List(Expression(Integer))

-
Hmm... now that's a rather complicated recurrence there. :) The only reason why I was wondering if it had a hypergeometric representation was so I could do Sister Celine Fasenmyer's method of finding recursion relations of a function with an explicit hypergeometric representation. I suppose it is up to me to verify the correctness and stability of this recurrence. Thanks! –  J. M. Aug 21 '10 at 13:57
I am wondering whether "the sum and the product of two holonomic functions is holonomic again" generalizes to several variables, in the sense that the sum and the tensor product of two non-faithful representations of a Weyl algebra is necessarily non-faithful again. –  darij grinberg Aug 21 '10 at 19:31
I don't know about representations of a Weyl algebra, but products and sums of multivariate holonomic generating functions are again holonomic. See (and that's in fact the reference I was looking for) Theorem B.2 and Theorem B.3 in Flajolet and Sedgewick algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html –  Martin Rubey Aug 21 '10 at 19:37
Now that's a great book. Of course, I was thinking too complicated - it's enough to consider vector spaces rather than Weyl modules. –  darij grinberg Aug 21 '10 at 20:16

Here's a negative result: I think I can show that there isn't a relation of the form:

$$a_n(x) =x C_n a_{n-1}+D_n a_{n-2}.$$

Through the properties of the Legendre polynomials, we find $D_n$ by proposing that the relation is true for $x=0$. Then we find $C_n$ by proposing that the relation is true in an integral. Then we show that the result isn't correct.

All the $a_i(x)$ are odd functions of $x$ for odd $i$, so $a_i(0)=0$, and for even $n$:

$$a_n(0)=P_n(0)-\frac{n-1}{n} P_{n-2}(0) =2(-1)^{n/2} \frac{(n-1)!!}{n!!}$$

using $P_n(0)=(-1)^{n/2} {(n-1)!!}/{n!!}$

So, if the relation is true for $x=0$, we know $D_n = -(n-1)/n$ for even $n$.

We know that

$$\int_{-1}^{1} \frac{P_n(x)}{\sqrt{1-x^2}} dx=\pi \left[ {\frac{(n-1)!!}{n!!}}\right] ^2$$

so after a bit of work I make it that $$\int_{-1}^{1} \frac{a_n(x)}{\sqrt{1-x^2}} dx= \frac{-\pi}{n-1} \left[ {\frac{(n-1)!!}{n!!}}\right] ^2$$ $$\int_{-1}^{1} \frac{x \ a_{n-1}(x)}{\sqrt{1-x^2}} dx= \frac{-\pi (n^2-3n+3)}{n(n-1)(n-3)} \left[ {\frac{(n-3)!!}{(n-2)!!}}\right] ^2$$ $$C_n=\frac{(n-1)^2(2n-3)}{(n^2-3n+3)n}$$

(after applying the integral to the relation). As far as I can tell, this does what it should -- I checked a specific example by typing into WolframAlpha: http://tinyurl.com/64pevxp , http://tinyurl.com/637ncou. However, it doesn't generate the correct $a_n$ (for example, http://tinyurl.com/6gthkyg is not http://tinyurl.com/6afuttz).

You could check my working (I've been working on paper with the odd bit of WolframAlpha, because that's all I've got), but then perhaps you never expected the recurrence relation to be that simple.

-
I pretty much expected there wouldn't be a three-term linear recurrence, but this doesn't preclude the existence of other many-term, possibly nonlinear, recurrences, yes? –  J. M. Aug 5 '11 at 5:32