Finding a recursion for a sum of Legendre polynomials - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T01:25:34Z http://mathoverflow.net/feeds/question/36207 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/36207/finding-a-recursion-for-a-sum-of-legendre-polynomials Finding a recursion for a sum of Legendre polynomials J. M. 2010-08-20T17:45:42Z 2011-07-17T17:36:47Z <p>The polynomial</p> <p>$a_n(x):=P_n(x)-\frac{n-1}{n}P_{n-2}(x)$</p> <p>where $P_n(x)$ is a Legendre polynomial came up while I was investigating methods for estimating the error in Gaussian quadrature.</p> <p>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$...</p> <p>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?</p> http://mathoverflow.net/questions/36207/finding-a-recursion-for-a-sum-of-legendre-polynomials/36209#36209 Answer by darij grinberg for Finding a recursion for a sum of Legendre polynomials darij grinberg 2010-08-20T18:24:44Z 2010-08-21T16:52:05Z <p>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.</p> <p><strong>The general background:</strong></p> <p>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:</p> <p>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.</p> <p>[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.]</p> <p><strong>Applications to the question:</strong></p> <p>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)$.</p> <p>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.</p> <p>Note that</p> <p>$\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$,</p> <p>where $U$ denotes the power series $\dfrac{1}{\sqrt{1-2xt+t^2}}=\sum\limits_{n=0}^{\infty}P_nt^n$.</p> <p>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$.)</p> http://mathoverflow.net/questions/36207/finding-a-recursion-for-a-sum-of-legendre-polynomials/36268#36268 Answer by Martin Rubey for Finding a recursion for a sum of Legendre polynomials Martin Rubey 2010-08-21T09:47:23Z 2010-08-21T19:29:20Z <p>(this is a variation on Darij's answer)</p> <p>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.<br> For a (very brief) summary, see <a href="http://arxiv.org/pdf/math/0702086.pdf" rel="nofollow">Table 1 of a paper on guessing</a> (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.</p> <p>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.</p> <p>Thus, to find such a recurrence (or differential equation), it is often easiest to use <a href="http://algo.inria.fr/libraries/papers/gfun.html" rel="nofollow">gfun for Maple</a> by Bruno Salvy and Paul Zimmermann, or the Mathematica equivalent by Mallinger (I think). Unfortunately, the FriCAS package described in <a href="http://arxiv.org/pdf/math/0702086.pdf" rel="nofollow">1</a> 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.</p> <p>However, you also asked, whether the solution is hypergeometric. To check this, you simply feed the recurrence you found below into Petkovsek's program <a href="http://www.fmf.uni-lj.si/~petkovsek/software.html" rel="nofollow">Hyper</a>, 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.)</p> <p>In case you are dealing with orthogonal polynomials, the <a href="http://www.cs.vu.nl/~rene/Onderzoek/AW.html" rel="nofollow">Askey Wilson scheme</a> by Koekoek and Swarttouw is a great reference to find the basic information.</p> <pre> (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)) </pre> http://mathoverflow.net/questions/36207/finding-a-recursion-for-a-sum-of-legendre-polynomials/70563#70563 Answer by ed-wynn for Finding a recursion for a sum of Legendre polynomials ed-wynn 2011-07-17T17:36:47Z 2011-07-17T17:36:47Z <p>Here's a negative result: I think I can show that there isn't a relation of the form: </p><p> $$a_n(x) =x C_n a_{n-1}+D_n a_{n-2}.$$ </p><p> 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.<br> </p><p> All the $a_i(x)$ are odd functions of $x$ for odd $i$, so $a_i(0)=0$, and for even $n$: </p><p> $$a_n(0)=P_n(0)-\frac{n-1}{n} P_{n-2}(0) =2(-1)^{n/2} \frac{(n-1)!!}{n!!}$$ </p><p> using $P_n(0)=(-1)^{n/2} {(n-1)!!}/{n!!}$ </p><p> So, if the relation is true for $x=0$, we know $D_n = -(n-1)/n$ for even $n$. </p><p> We know that </p><p> $$\int_{-1}^{1} \frac{P_n(x)}{\sqrt{1-x^2}} dx=\pi \left[ {\frac{(n-1)!!}{n!!}}\right] ^2$$ </p><p> 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}$$</p> <p></p><p> (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: <a href="http://tinyurl.com/64pevxp" rel="nofollow">http://tinyurl.com/64pevxp</a> , <a href="http://tinyurl.com/637ncou" rel="nofollow">http://tinyurl.com/637ncou</a>. However, it doesn't generate the correct $a_n$ (for example, <a href="http://tinyurl.com/6gthkyg" rel="nofollow">http://tinyurl.com/6gthkyg</a> is not <a href="http://tinyurl.com/6afuttz" rel="nofollow">http://tinyurl.com/6afuttz</a>). </p><p> 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.</p>