Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Polynomial solutions of P-recursive equations
open-in-new
<h2 id="degree-bound">Degree bound</h2> <p>Let K {\textstyle \mathbb {K} } be a <a href="/facts/Field_(mathematics)/xAjAS4ko">field</a> of characteristic zero and ∑ k = 0 r p k ( n ) y ( n + k ) = f ( n ) {\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)} a <a href="/facts/P-recursive_equation/U03dgoPw">recurrence equation</a> of order r {\textstyle r} with polynomial coefficients p k ∈ K [ n ] {\textstyle p_{k}\in \mathbb {K} [n]} , polynomial right-hand side f ∈ K [ n ] {\textstyle f\in \mathbb {K} [n]} and unknown polynomial sequence y ( n ) ∈ K [ n ] {\displaystyle y(n)\in \mathbb {K} [n]} . Furthermore deg ( p ) {\textstyle \deg(p)} denotes the degree of a polynomial p ∈ K [ n ] {\textstyle p\in \mathbb {K} [n]} (with deg ( 0 ) = − ∞ {\textstyle \deg(0)=-\infty } for the zero polynomial) and lc ( p ) {\textstyle {\text{lc}}(p)} denotes the leading coefficient of the polynomial. Moreover let q i = ∑ k = i r ( k i ) p k , b = max i = 0 , … , r ( deg ( q i ) − i ) , α ( n ) = ∑ i = 0 , … , r deg ( q i ) − i = b lc ( q i ) n i _ , d α = max { n ∈ N : α ( n ) = 0 } ∪ { − ∞ } {\displaystyle {\begin{aligned}q_{i}&=\sum _{k=i}^{r}{\binom {k}{i}}p_{k},&b&=\max _{i=0,\dots ,r}(\deg(q_{i})-i),\\\alpha (n)&=\sum _{i=0,\dots ,r \atop \deg(q_{i})-i=b}{\text{lc}}(q_{i})n^{\underline {i}},&d_{\alpha }&=\max\{n\in \mathbb {N} \,:\,\alpha (n)=0\}\cup \{-\infty \}\end{aligned}}} for i = 0 , … , r {\textstyle i=0,\dots ,r} where n i _ = n ( n − 1 ) ⋯ ( n − i + 1 ) {\textstyle n^{\underline {i}}=n(n-1)\cdots (n-i+1)} denotes the <a href="/facts/Falling_and_rising_factorials/sAxnmGoC">falling factorial</a> and N {\textstyle \mathbb {N} } the set of nonnegative integers. Then deg ( y ) ≤ max { deg ( f ) − b , − b − 1 , d α } {\textstyle \deg(y)\leq \max\{\deg(f)-b,-b-1,d_{\alpha }\}} . This is called a degree bound for the polynomial solution y {\textstyle y} . This bound was shown by Abramov and Petkovšek.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a><a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a><a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a><a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p> <h2 id="algorithm">Algorithm</h2> <p>The algorithm consists of two steps. In a first step the <i>degree bound</i> is computed. In a second step an <i>ansatz</i> with a polynomial y {\textstyle y} of that degree with arbitrary coefficients in K {\textstyle \mathbb {K} } is made and plugged into the recurrence equation. Then the different powers are compared and a system of linear equations for the coefficients of y {\textstyle y} is set up and solved. This is called the <i>method undetermined coefficients</i>.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> The algorithm returns the general polynomial solution of a recurrence equation. </p> algorithm polynomial_solutions is input: Linear recurrence equation ∑ k = 0 r p k ( n ) y ( n + k ) = f ( n ) , p k , f ∈ K [ n ] , p 0 , p r ≠ 0 {\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n),p_{k},f\in \mathbb {K} [n],p_{0},p_{r}\neq 0} . output: The general polynomial solution y {\textstyle y} if there are any solutions, otherwise false. for i = 0 , … , r {\textstyle i=0,\dots ,r} do q i = ∑ k = i r ( k i ) p k {\textstyle q_{i}=\sum _{k=i}^{r}{\binom {k}{i}}p_{k}} repeat b = max i = 0 , … , r ( deg ( q i ) − i ) {\textstyle b=\max _{i=0,\dots ,r}(\deg(q_{i})-i)} α ( n ) = ∑ i = 0 , … , r deg ( q i ) − i = b lc ( q i ) n i _ {\textstyle \alpha (n)=\sum _{i=0,\dots ,r \atop \deg(q_{i})-i=b}{\text{lc}}(q_{i})n^{\underline {i}}} d α = max { n ∈ N : α ( n ) = 0 } ∪ { − ∞ } {\textstyle d_{\alpha }=\max\{n\in \mathbb {N} \,:\,\alpha (n)=0\}\cup \{-\infty \}} d = max { deg ( f ) − b , − b − 1 , d α } {\textstyle d=\max\{\deg(f)-b,-b-1,d_{\alpha }\}} y ( n ) = ∑ j = 0 d y j n j {\textstyle y(n)=\sum _{j=0}^{d}y_{j}n^{j}} with unknown coefficients y j ∈ K {\textstyle y_{j}\in \mathbb {K} } for j = 0 , … , d {\textstyle j=0,\dots ,d} Compare coefficients of polynomials ∑ k = 0 r p k ( n ) y ( n + k ) {\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)} and f ( n ) {\textstyle f(n)} to get possible values for y j , j = 0 , … , d {\textstyle y_{j},j=0,\dots ,d} if there are possible values for y j {\textstyle y_{j}} then return general solution y {\textstyle y} else return false end if <h2 id="example">Example</h2> <p>Applying the formula for the degree bound on the recurrence equation ( n 2 − 2 ) y ( n ) + ( − n 2 + 2 n ) y ( n + 1 ) = 2 n , {\displaystyle (n^{2}-2)\,y(n)+(-n^{2}+2n)\,y(n+1)=2n,} over Q {\textstyle \mathbb {Q} } yields deg ( y ) ≤ 2 {\textstyle \deg(y)\leq 2} . Hence one can use an ansatz with a quadratic polynomial y ( n ) = y 2 n 2 + y 1 n + y 0 {\textstyle y(n)=y_{2}n^{2}+y_{1}n+y_{0}} with y 0 , y 1 , y 2 ∈ Q {\textstyle y_{0},y_{1},y_{2}\in \mathbb {Q} } . Plugging this ansatz into the original recurrence equation leads to 2 n = ( n 2 − 2 ) y ( n ) + ( − n 2 + 2 n ) y ( n + 1 ) = ( y 1 + y 2 ) n 2 + ( 2 y 0 + 2 y 2 ) n − 2 y 0 . {\displaystyle 2n=(n^{2}-2)\,y(n)+(-n^{2}+2n)\,y(n+1)=(y_{1}+y_{2})\,n^{2}+(2y_{0}+2y_{2})\,n-2y_{0}.} This is equivalent to the following system of linear equations ( 0 1 1 2 0 2 − 2 0 0 ) ( y 0 y 1 y 2 ) = ( 0 2 0 ) {\displaystyle {\begin{aligned}{\begin{pmatrix}0&1&1\\2&0&2\\-2&0&0\end{pmatrix}}{\begin{pmatrix}y_{0}\\y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}0\\2\\0\end{pmatrix}}\end{aligned}}} with the solution y 0 = 0 , y 1 = − 1 , y 2 = 1 {\textstyle y_{0}=0,y_{1}=-1,y_{2}=1} . Therefore the only polynomial solution is y ( n ) = n 2 − n {\textstyle y(n)=n^{2}-n} . </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Abramov, Sergei A. (1989). "Problems in computer algebra that are connected with a search for polynomial solutions of linear differential and difference equations". Moscow University Computational Mathematics and Cybernetics. 3. <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Petkovšek, Marko (1992). "Hypergeometric solutions of linear recurrences with polynomial coefficients". Journal of Symbolic Computation. 14 (2–3): 243–264. doi:10.1016/0747-7171(92)90038-6. ISSN 0747-7171. <a href="https://doi.org/10.1016%2F0747-7171%2892%2990038-6" target="_blank">https://doi.org/10.1016%2F0747-7171%2892%2990038-6</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Abramov, Sergei A.; Bronstein, Manuel; Petkovšek, Marko (1995). "On polynomial solutions of linear operator equations". Proceedings of the 1995 international symposium on Symbolic and algebraic computation - ISSAC '95. ACM. pp. 290–296. CiteSeerX 10.1.1.46.9373. doi:10.1145/220346.220384. ISBN 978-0897916998. S2CID 14963237. <a href="978-0897916998" target="_blank">978-0897916998</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Abramov, Sergei A. (1989). "Problems in computer algebra that are connected with a search for polynomial solutions of linear differential and difference equations". Moscow University Computational Mathematics and Cybernetics. 3. <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Petkovšek, Marko (1992). "Hypergeometric solutions of linear recurrences with polynomial coefficients". Journal of Symbolic Computation. 14 (2–3): 243–264. doi:10.1016/0747-7171(92)90038-6. ISSN 0747-7171. <a href="https://doi.org/10.1016%2F0747-7171%2892%2990038-6" target="_blank">https://doi.org/10.1016%2F0747-7171%2892%2990038-6</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Abramov, Sergei A.; Bronstein, Manuel; Petkovšek, Marko (1995). "On polynomial solutions of linear operator equations". Proceedings of the 1995 international symposium on Symbolic and algebraic computation - ISSAC '95. ACM. pp. 290–296. CiteSeerX 10.1.1.46.9373. doi:10.1145/220346.220384. ISBN 978-0897916998. S2CID 14963237. <a href="978-0897916998" target="_blank">978-0897916998</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Weixlbaumer, Christian (2001). Solutions of difference equations with polynomial coefficients. Diploma Thesis, Johannes Kepler Universität Linz <a href="https://www.risc.jku.at/research/combinat/software/DiffTools/pub/weixlbaumer01.pdf" target="_blank">https://www.risc.jku.at/research/combinat/software/DiffTools/pub/weixlbaumer01.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Petkovšek, Marko; Wilf, Herbert S.; Zeilberger, Doron (1996). A=B. A K Peters. ISBN 978-1568810638. OCLC 33898705. <a href="978-1568810638" target="_blank">978-1568810638</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> </ol>