Petkovšek's algorithm is a computer algebra algorithm that computes a basis of hypergeometric terms solution of its input linear recurrence equation with polynomial coefficients. Equivalently, it computes a first order right factor of linear difference operators with polynomial coefficients. This algorithm is implemented in all the major computer algebra systems.
Given the linear recurrence
4
(
n
+
2
)
(
2
n
+
3
)
(
2
n
+
5
)
a
(
n
+
2
)
−
12
(
2
n
+
3
)
(
9
n
2
+
27
n
+
22
)
a
(
n
+
1
)
+
81
(
n
+
1
)
(
3
n
+
2
)
(
3
n
+
4
)
a
(
n
)
=
0
,
the algorithm finds two linearly independent hypergeometric terms that are solution:
Γ
(
n
+
1
)
Γ
(
n
+
3
/
2
)
(
27
4
)
n
,
Γ
(
n
+
2
/
3
)
Γ
(
n
+
4
/
3
)
Γ
(
n
+
3
/
2
)
Γ
(
n
+
1
)
(
27
4
)
n
.
(Here,
Γ
denotes Euler's Gamma function.) Note that the second solution is also a binomial coefficient
(
3
n
+
1
n
)
, but it is not the aim of this algorithm to produce binomial expressions.
Given the sum
a
(
n
)
=
∑
k
=
0
n
(
n
k
)
2
(
n
+
k
k
)
2
,
coming from Apéry's proof of the irrationality of
ζ
(
3
)
, Zeilberger'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.
Given this recurrence, the algorithm does not return any hypergeometric solution, which proves that
a
(
n
)
does not simplify to a hypergeometric term.
