Petkovšek's algorithm

<h2 id="gosper-petkovek-representation">Gosper-Petkovšek representation</h2>
Let 
 
 
 
 
 K
 
 
 
 {\textstyle \mathbb {K} }
 
 be a <a href="/facts/Field_(mathematics)/xAjAS4ko">field</a> of <a href="/facts/Characteristic_(algebra)/D2VzcQaG">characteristic</a> zero. A nonzero sequence 
 
 
 
 y
 (
 n
 )
 
 
 {\textstyle y(n)}
 
 is called hypergeometric if the ratio of two consecutive terms is <a href="/facts/Rational_function/2nJGu0Ko">rational</a>, i.e. 
 
 
 
 y
 (
 n
 +
 1
 )
 
 /
 
 y
 (
 n
 )
 ∈
 
 K
 
 (
 n
 )
 
 
 {\textstyle y(n+1)/y(n)\in \mathbb {K} (n)}
 
. The Petkovšek algorithm uses as key concept that this rational function has a specific representation, namely the Gosper-Petkovšek normal form. Let 
 
 
 
 r
 (
 n
 )
 ∈
 
 K
 
 [
 n
 ]
 
 
 {\textstyle r(n)\in \mathbb {K} [n]}
 
 be a nonzero rational function. Then there exist monic <a href="/facts/Ring_of_polynomial_functions/q99CvhPj">polynomials</a> 
 
 
 
 a
 ,
 b
 ,
 c
 ∈
 
 K
 
 [
 n
 ]
 
 
 {\textstyle a,b,c\in \mathbb {K} [n]}
 
 and 
 
 
 
 0
 ≠
 z
 ∈
 
 K
 
 
 
 {\textstyle 0\neq z\in \mathbb {K} }
 
 such that

 
 
 
 r
 (
 n
 )
 =
 z
 
 
 
 a
 (
 n
 )
 
 
 b
 (
 n
 )
 
 
 
 
 
 
 c
 (
 n
 +
 1
 )
 
 
 c
 (
 n
 )
 
 
 
 
 
 {\displaystyle r(n)=z{\frac {a(n)}{b(n)}}{\frac {c(n+1)}{c(n)}}}

and

<ol><li>
 
 
 
 gcd
 (
 a
 (
 n
 )
 ,
 b
 (
 n
 +
 k
 )
 )
 =
 1
 
 
 {\textstyle \gcd(a(n),b(n+k))=1}
 
 for every nonnegative integer 
 
 
 
 k
 ∈
 
 N
 
 
 
 {\textstyle k\in \mathbb {N} }
 
,</li>
<li>
 
 
 
 gcd
 (
 a
 (
 n
 )
 ,
 c
 (
 n
 )
 )
 =
 1
 
 
 {\textstyle \gcd(a(n),c(n))=1}
 
 and</li>
<li>
 
 
 
 gcd
 (
 b
 (
 n
 )
 ,
 c
 (
 n
 +
 1
 )
 )
 =
 1
 
 
 {\textstyle \gcd(b(n),c(n+1))=1}
 
.</li></ol>
This representation of 
 
 
 
 r
 (
 n
 )
 
 
 {\textstyle r(n)}
 
 is called Gosper-Petkovšek normal form. These polynomials can be computed explicitly. This construction of the representation is an essential part of <a href="/facts/Gosper%2527s_algorithm/Iu7Jc8zQ">Gosper's algorithm</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> Petkovšek added the conditions 2. and 3. of this representation which makes this normal form unique.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<h2 id="algorithm">Algorithm</h2>
Using the Gosper-Petkovšek representation one can transform the original recurrence equation into a recurrence equation for a polynomial sequence 
 
 
 
 c
 (
 n
 )
 
 
 {\textstyle c(n)}
 
. The other polynomials 
 
 
 
 a
 (
 n
 )
 ,
 b
 (
 n
 )
 
 
 {\textstyle a(n),b(n)}
 
 can be taken as the monic factors of the first coefficient polynomial 
 
 
 
 
 p
 
 0
 
 
 (
 n
 )
 
 
 {\textstyle p_{0}(n)}
 
 resp. the last coefficient polynomial shifted 
 
 
 
 
 p
 
 r
 
 
 (
 n
 −
 r
 +
 1
 )
 
 
 {\textstyle p_{r}(n-r+1)}
 
. Then 
 
 
 
 z
 
 
 {\textstyle z}
 
 has to fulfill a certain <a href="/facts/Algebraic_equation/1QauIGxs">algebraic equation</a>. Taking all the possible finitely many triples 
 
 
 
 (
 a
 (
 n
 )
 ,
 b
 (
 n
 )
 ,
 z
 )
 
 
 {\textstyle (a(n),b(n),z)}
 
 and computing the corresponding <a href="/facts/Polynomial_solutions_of_P-recursive_equations/HTtg2wGV">polynomial solution</a> of the transformed recurrence equation 
 
 
 
 c
 (
 n
 )
 
 
 {\textstyle c(n)}
 
 gives a hypergeometric solution if one exists.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
In the following pseudocode the degree of a polynomial 
 
 
 
 p
 (
 n
 )
 ∈
 
 K
 
 [
 n
 ]
 
 
 {\textstyle p(n)\in \mathbb {K} [n]}
 
 is denoted by 
 
 
 
 deg
 ⁡
 (
 p
 (
 n
 )
 )
 
 
 {\textstyle \deg(p(n))}
 
 and the coefficient of 
 
 
 
 
 n
 
 d
 
 
 
 
 {\textstyle n^{d}}
 
 is denoted by 
 
 
 
 
 coeff
 
 (
 p
 (
 n
 )
 ,
 
 n
 
 d
 
 
 )
 
 
 {\textstyle {\text{coeff}}(p(n),n^{d})}
 
.

algorithm petkovsek is
 input: Linear recurrence equation 
 
 
 
 
 ∑
 
 k
 =
 0
 
 
 r
 
 
 
 p
 
 k
 
 
 (
 n
 )
 
 y
 (
 n
 +
 k
 )
 =
 0
 ,
 
 p
 
 k
 
 
 ∈
 
 K
 
 [
 n
 ]
 ,
 
 p
 
 0
 
 
 ,
 
 p
 
 r
 
 
 ≠
 0
 
 
 {\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=0,p_{k}\in \mathbb {K} [n],p_{0},p_{r}\neq 0}
 
.
 output: A hypergeometric solution 
 
 
 
 y
 
 
 {\textstyle y}
 
 if there are any hypergeometric solutions.

for each monic divisor 
  
    
      
        a
        (
        n
        )
      
    
    {\textstyle a(n)}
  
 of 
  
    
      
        
          p
          
            0
          
        
        (
        n
        )
      
    
    {\textstyle p_{0}(n)}
  
 do
        for each monic divisor 
  
    
      
        b
        (
        n
        )
      
    
    {\textstyle b(n)}
  
 of 
  
    
      
        
          p
          
            r
          
        
        (
        n
        −
        r
        +
        1
        )
      
    
    {\textstyle p_{r}(n-r+1)}
  
 do
            for each 
  
    
      
        k
        =
        0
        ,
        …
        ,
        r
      
    
    {\textstyle k=0,\dots ,r}
  
 do
                
  
    
      
        
          
            
              
                p
                ~
              
            
          
          
            k
          
        
        (
        n
        )
        =
        
          p
          
            k
          
        
        (
        n
        )
        
          ∏
          
            j
            =
            0
          
          
            k
            −
            1
          
        
        a
        (
        n
        +
        j
        )
        
          ∏
          
            i
            =
            k
          
          
            r
            −
            1
          
        
        b
        (
        n
        +
        i
        )
      
    
    {\textstyle {\tilde {p}}_{k}(n)=p_{k}(n)\prod _{j=0}^{k-1}a(n+j)\prod _{i=k}^{r-1}b(n+i)}

d
        =
        
          max
          
            k
            =
            0
            ,
            …
            ,
            r
          
        
        deg
        ⁡
        (
        
          
            
              
                p
                ~
              
            
          
          
            k
          
        
        (
        n
        )
        )
      
    
    {\textstyle d=\max _{k=0,\dots ,r}\deg({\tilde {p}}_{k}(n))}

for each root 
  
    
      
        z
      
    
    {\textstyle z}
  
 of 
  
    
      
        
          ∑
          
            k
            =
            0
          
          
            r
          
        
        
          coeff
        
        (
        
          
            
              
                p
                ~
              
            
          
          
            k
          
        
        (
        n
        )
        ,
        
          n
          
            d
          
        
        )
        
          z
          
            k
          
        
      
    
    {\textstyle \sum _{k=0}^{r}{\text{coeff}}({\tilde {p}}_{k}(n),n^{d})z^{k}}
  
 do
            Find non-zero polynomial solution 
  
    
      
        c
        (
        n
        )
      
    
    {\textstyle c(n)}
  
 of 
  
    
      
        
          ∑
          
            k
            =
            0
          
          
            r
          
        
        
          z
          
            k
          
        
        
        
          
            
              
                p
                ~
              
            
          
          
            k
          
        
        (
        n
        )
        
        c
        (
        n
        +
        k
        )
        =
        0
      
    
    {\textstyle \sum _{k=0}^{r}z^{k}\,{\tilde {p}}_{k}(n)\,c(n+k)=0}

if such a non-zero solution 
  
    
      
        c
        (
        n
        )
      
    
    {\textstyle c(n)}
  
 exists then
                
  
    
      
        r
        (
        n
        )
        =
        z
        
        a
        (
        n
        )
        
          /
        
        b
        (
        n
        )
        
        c
        (
        n
        +
        1
        )
        
          /
        
        c
        (
        n
        )
      
    
    {\textstyle r(n)=z\,a(n)/b(n)\,c(n+1)/c(n)}

return a non-zero solution 
  
    
      
        y
        (
        n
        )
      
    
    {\textstyle y(n)}
  
 of 
  
    
      
        y
        (
        n
        +
        1
        )
        =
        r
        (
        n
        )
        
        y
        (
        n
        )
      
    
    {\textstyle y(n+1)=r(n)\,y(n)}

If one does not end if a solution is found it is possible to combine all hypergeometric solutions to get a general hypergeometric solution of the recurrence equation, i.e. a generating set for the kernel of the recurrence equation in the linear span of hypergeometric sequences.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
Petkovšek also showed how the inhomogeneous problem can be solved. He considered the case where the right-hand side of the recurrence equation is a sum of hypergeometric sequences. After grouping together certain hypergeometric sequences of the right-hand side, for each of those groups a certain recurrence equation is solved for a rational solution. These rational solutions can be combined to get a particular solution of the inhomogeneous equation. Together with the general solution of the homogeneous problem this gives the general solution of the inhomogeneous problem.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h2 id="examples">Examples</h2>
<h3>Signed permutation matrices</h3>
The number of <a href="/facts/Generalized_permutation_matrix/K6rYn22q">signed permutation matrices</a> of size 
 
 
 
 n
 ×
 n
 
 
 {\textstyle n\times n}
 
 can be described by the sequence 
 
 
 
 y
 (
 n
 )
 
 
 {\textstyle y(n)}
 
 which is determined by the recurrence equation
 
 
 
 4
 (
 n
 +
 1
 
 )
 
 2
 
 
 
 y
 (
 n
 )
 +
 2
 
 y
 (
 n
 +
 1
 )
 +
 (
 −
 1
 )
 
 y
 (
 n
 +
 2
 )
 =
 0
 
 
 {\displaystyle 4(n+1)^{2}\,y(n)+2\,y(n+1)+(-1)\,y(n+2)=0}
 
over 
 
 
 
 
 Q
 
 
 
 {\textstyle \mathbb {Q} }
 
. Taking 
 
 
 
 a
 (
 n
 )
 =
 n
 +
 1
 ,
 b
 (
 n
 )
 =
 1
 
 
 {\textstyle a(n)=n+1,b(n)=1}
 
 as monic divisors of 
 
 
 
 
 p
 
 0
 
 
 (
 n
 )
 =
 4
 (
 n
 +
 1
 
 )
 
 2
 
 
 ,
 
 p
 
 2
 
 
 (
 n
 )
 =
 −
 1
 
 
 {\textstyle p_{0}(n)=4(n+1)^{2},p_{2}(n)=-1}
 
 respectively, one gets 
 
 
 
 z
 =
 ±
 2
 
 
 {\textstyle z=\pm 2}
 
. For 
 
 
 
 z
 =
 2
 
 
 {\textstyle z=2}
 
 the corresponding recurrence equation which is solved in Petkovšek's algorithm is
 
 
 
 4
 (
 n
 +
 1
 
 )
 
 2
 
 
 
 c
 (
 n
 )
 +
 4
 (
 n
 +
 1
 )
 
 c
 (
 n
 +
 1
 )
 −
 4
 (
 n
 +
 1
 )
 (
 n
 +
 2
 )
 
 c
 (
 n
 +
 2
 )
 =
 0.
 
 
 {\displaystyle 4(n+1)^{2}\,c(n)+4(n+1)\,c(n+1)-4(n+1)(n+2)\,c(n+2)=0.}
 
This recurrence equation has the polynomial solution 
 
 
 
 c
 (
 n
 )
 =
 
 c
 
 0
 
 
 
 
 {\textstyle c(n)=c_{0}}
 
 for an arbitrary 
 
 
 
 
 c
 
 0
 
 
 ∈
 
 Q
 
 
 
 {\textstyle c_{0}\in \mathbb {Q} }
 
. Hence 
 
 
 
 r
 (
 n
 )
 =
 2
 (
 n
 +
 1
 )
 
 
 {\textstyle r(n)=2(n+1)}
 
 and 
 
 
 
 y
 (
 n
 )
 =
 
 2
 
 n
 
 
 
 n
 !
 
 
 {\textstyle y(n)=2^{n}\,n!}
 
 is a hypergeometric solution. In fact it is (up to a constant) the only hypergeometric solution and describes the number of signed permutation matrices.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>

<h3>Irrationality of 
 
 
 
 ζ
 (
 3
 )
 
 
 {\displaystyle \zeta (3)}
 
</h3>
Given the sum

a
        (
        n
        )
        =
        
          ∑
          
            k
            =
            0
          
          
            n
          
        
        
          
            
              
                
                  (
                
                
                  n
                  k
                
                
                  )
                
              
            
            
              2
            
          
          
            
              
                
                  (
                
                
                  
                    n
                    +
                    k
                  
                  k
                
                
                  )
                
              
            
            
              2
            
          
        
        ,
      
    
    {\displaystyle a(n)=\sum _{k=0}^{n}{{\binom {n}{k}}^{2}{\binom {n+k}{k}}^{2}},}

coming from <a href="/facts/Roger_Ap%25C3%25A9ry/3Gu2eMDk">Apéry</a>'s proof of the irrationality of 
 
 
 
 ζ
 (
 3
 )
 
 
 {\displaystyle \zeta (3)}
 
, <a href="/facts/Doron_Zeilberger/M90TmhyY">Zeilberger</a>'s algorithm computes the linear recurrence

(
        n
        +
        2
        
          )
          
            3
          
        
        
        a
        (
        n
        +
        2
        )
        −
        (
        17
        
          n
          
            2
          
        
        +
        51
        n
        +
        39
        )
        (
        2
        n
        +
        3
        )
        
        a
        (
        n
        +
        1
        )
        +
        (
        n
        +
        1
        
          )
          
            3
          
        
        
        a
        (
        n
        )
        =
        0.
      
    
    {\displaystyle (n+2)^{3}\,a(n+2)-(17n^{2}+51n+39)(2n+3)\,a(n+1)+(n+1)^{3}\,a(n)=0.}

Given this recurrence, the algorithm does not return any hypergeometric solution, which proves that 
 
 
 
 a
 (
 n
 )
 
 
 {\displaystyle a(n)}
 
 does not simplify to a <a href="/facts/Hypergeometric_identity/YEFYxhjr">hypergeometric term</a>.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">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:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Gosper, R. William (1978). "Decision procedure for indefinite hypergeometric summation". Proc. Natl. Acad. Sci. USA. 75 (1): 40–42. doi:10.1073/pnas.75.1.40. PMC 411178. PMID 16592483. S2CID 26361864. <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC411178" target="_blank">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC411178</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">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:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">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:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Petkovšek, Marko; Wilf, Herbert S.; Zeilberger, Doron (1996). A=B. A K Peters. ISBN 1568810636. OCLC 33898705. <a href="1568810636" target="_blank">1568810636</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Kauers, Manuel; Paule, Peter (2011). The concrete tetrahedron : symbolic sums, recurrence equations, generating functions, asymptotic estimates. Wien: Springer. ISBN 9783709104453. OCLC 701369215. <a href="9783709104453" target="_blank">9783709104453</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">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:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">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:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">"A000165 - OEIS". oeis.org. Retrieved 2018-07-02. <a href="https://oeis.org/A000165" target="_blank">https://oeis.org/A000165</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Petkovšek, Marko; Wilf, Herbert S.; Zeilberger, Doron (1996). A=B. A K Peters. ISBN 1568810636. OCLC 33898705. <a href="1568810636" target="_blank">1568810636</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
</ol>

Petkovšek's algorithm open-in-new

Petkovšek's algorithm