{'fraction_non_alphanumeric': 0.05414338080644192, 'fraction_numerical': 0.019800492758848626, 'mean_word_length': 3.521532400489064, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 25, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Closed form solutions of linear difference equations in terms of symmetric products

In this paper we show how to find a closed form solution for third order difference operators in terms of solutions of second order operators. This work is an extension of previous results on finding closed form solutions of recurrence equations and a counterpart to existing results on differential equations. As motivation and application for this work, we discuss the problem of proving positivity of sequences given merely in terms of their defining recurrence relation. The main advantage of the present approach to earlier methods attacking the same problem is that our algorithm provides human-readable and verifiable, i.e., certified proofs.


Introduction
This paper presents an extension of the algorithm solver [3,4,6] that returns closed form solutions for second order linear difference equations to third order linear difference equations. The solutions that we are looking for are in terms of (finite) sums of squares. This is motivated by applying the algorithm for proving inequalities on special functions, i.e., on expressions that may be defined in terms of linear difference equations with polynomial coefficients. Conjectures about positivity of special functions inequalities arise in many applications in mathematics and science. Proving them usually requires profound knowledge on relations between these special functions. It is well known that there exist many algorithms for proving and finding special function identities [30,8,20,17]. For automated proving of special functions inequalities only few approaches exist. Gerhold and Kauers [12,15] introduced a method that is based on Cylindrical Algebraic Decomposition (CAD). This method has been proven to work well on many non-trivial examples [13,21], but even though correctness is easy to be seen, termination cannot be guaranteed, hence it is not an algorithm in the strict sense. A first attempt to clarify the latter issue has been made in [16]. One of the features of proofs of special functions identities is that they usually come with a certificate, i.e., some easy to check identity that verifies the proof. The CAD-based approach can not hope to have a similar certificate in the near future. The method presented here is a first step toward human readable proofs of special functions inequalities, although admittedly a representation in terms of sums of squares with positive coefficients is not expected to exist for any given input. Besides this application, the results presented are of independent interest as they provide difference case counterparts to results obtained for the differential case [22,28].
First we review the available results in the differential case. Let k be a differential field and L d ∈ k[∂], ∂ = d/dx be a linear homogeneous third order differential operator. Singer [22] characterizes when solutions of L d can be written in terms of solutions of a second order operator ink [∂]. Van Hoeij [28] handles the similar problem when the coefficients of the second order operator are restricted to k and shows that it will be either of the following cases.
Case 1 L d is the symmetric square of a second order operator K d ∈ k[∂] Case 2 L d is gauge equivalent to a symmetric square of a second order operator The definitions of symmetric products and gauge equivalence are recalled in sections 2.3 and 2.4 below. The algorithm given in [28] returns a second order differential operator, K d ∈ k[d/dx], and a gauge transformation in k[∂] that sends solutions of the symmetric squares of K d to solutions of L d for Case 2.
In the differential case, the symmetric square of L d has order 5 if and only if we are in Case 1. In this case, there is a simple formula that gives K d . Case 2 is equivalent to the symmetric square of L d having order 6 and a first order right-hand side factor in k[∂] as well as a certain conic of L d ( [22,Equation 4.2.1]) having a non-zero solution in k. Since for k = C(x) this conic is solvable over C(x), the last condition becomes trivial in this case. The algorithm given in [28] in the first step checks the order of the symmetric square of L d to distinguish the cases.
The difference case behaves differently; here we denote by D = C(x)[τ ] the ring of linear difference operators, where τ denotes the shift operator. Example 2.15 shows that the cases can not be distinguished according to the order of the symmetric squares when the coefficients are in C(x). To set up a counterpart theorem for difference equations, this example shows that we need one more transformation than that in the differential case. Furthermore in Case 1, the algorithm for finding the second order operator is more complicated than in the differential case.
Summarizing, the ideas used in the differential case can not be carried over immediately to the difference case. Furthermore our aim is to have a closed form solution of the given input. Hence, if a factorization is found that is not solvable, this fails to satisfy our goal. Thus we build on the ideas of the algorithm solver [3,4,6]. Here we say that a function is in closed form if it is a linear combination of elementary functions, special functions or hypergeometric functions over C(x). For instance the modified Bessel function of the first kind is a closed form solution of the second order operator L b := zτ 2 − (2x + 2)τ + x + z.
The algorithm solver returns closed form solutions for second order linear difference operators. The main idea of solver is to map the given operator L 1 to an operator L 2 of which a solution is known. This transformation is a bijective map, called GT-transformation, that sends solutions of L 1 to solutions of L 2 . If a closed form solution to one of the operators is known, then by means of this transformation the solution of the second operator can be constructed. For this purpose a table with second order operators including parameters together with characteristic data (local data) has been constructed. This local data can be computed for the given operator, the corresponding equivalent operator is found by table look-up. Then by comparing parameters of the local data the GT-transformation can be constructed. The characteristic data is described in Section 3. To cover the extension described here the table has been extended so that we can give closed form solutions of certain third order linear difference operators.

Preliminary
In this section we introduce notations used in this paper and recall some known facts [4,6,20,26] about difference operators. Additionally Cases 1 and 2 above are carried over to the difference case for algebraic extensions in Theorem 2.18 below.

Ring of difference oprators
be the ring of linear difference operators with coefficients in C(x), where τ is the shift operator acting on x by τ (x) = x+1. Then D is a noncommutative ring where For L = a d (x)τ d + · · · + a 1 (x)τ + a 0 (x) ∈ D with a d = 0, we say that L has order d and write ord(L) = d. If furthermore a 0 = 0 then L is said to be a normal operator. In this paper we will assume all operators to be normal. The adjoint operator of L is defined by and thus right-hand side factors of L correspond to left-hand side factors of L * . We say that a third order operator L is irreducible in D if both L and L * have no first order right-hand side factor in D.
A second order operator Thus, if K is a normal but not full operator, then b 1 = 0.

Ring of sequences
With the above termwise addition and multiplication, C N forms a C-algebra. We define the action of τ on Then it is easy to verify that s is a unit in S, i.e. s is invertible in S, if and only if s ∈ S has only finitely many zeros. If f ∈ C(x), then the image of f in S and the action of τ on S are well defined. This way we can embed C(x) to S and call s ∈ S rational if there exist g(x) ∈ C(x) and N ∈ N such that g(i) = s(i) for all i ≥ N . S[τ ] forms a ring of difference operators and D is embedded in S[τ ].
We say Thus for a normal operator L ∈ D, V (L) forms a C-vector space with a basis {v i ∈ S | 1 ≤ i ≤ ord(L)}. There is a simple formula if one of the operators has order 1. Let L = a d (x)τ d + · · · + · · · + a 1 (x)τ + a 0 (x) ∈ D and r(x) ∈ C(x). Then

Term equivalence
(1) Suppose L ∈ D and s ∈ S. Then the above formula gives an operatorL = L (τ − s) ∈ S[τ ] such that V (L) = {hu | L(u) = 0} where h ∈ S is a solution of τ − s. If L (τ − s) ∈ D then it is easy to see that s is rational.
Such a T is called the term transformation from L 1 to L 2 .
If L 1 and L 2 are term equivalent and τ −r is the term transformation then V (L 2 ) = {hv | h ∈ V (τ − r), v ∈ V (L 1 )}. Suppose L 1 and a term transformation T are given, then L 2 can be obtained by (1).

Gauge equivalence
Let L 1 , L 2 ∈ D be two given operators, where a closed form solution u of L 1 is known. If furthermore an operator G ∈ D can be determined sucht that G(u) is solution of L 2 , then a closed form solution of L 2 can be written as a linear combination of shifts of u over C(x). Such a transformation G is called a gauge transformation and L 1 and L 2 are said to be gauge equivalent if such a transformation exists.
Note that G is not required to be a normal operator. Suppose we are given a gauge transformation G where ord(G) ≥ ord(L 1 ). Then there exist Q,Ĝ ∈ D with ord(Ĝ) < ord(L 1 ) such that G = QL 1 +Ĝ. The remainder G is also a gauge transformation that acts in the same way as G on V (L 1 ). Hence, w.l.o.g., we may assume that ord(G) < ord(L 1 ).
Let GCRD(L, M ) denote the greatest common right divisor of L, M ∈ D. Since G is a bijection, any non zero solution u of L 1 does not map to zero by G. Thus, L 1 and G have no nontrivial common right hand factor, i.e. GCRD(L 1 , G) = 1. Using the extended Euclidean algorithmG,L 1 ∈ D can be determined such thatGG+L 1 L 1 = 1. ThenGG is the identity on V (L 1 ) andG is an inverse of G that sends V (L 2 ) → V (L 1 ) bijectively.
Definition 2.6. Two operators L 1 and L 2 with the same order are called gauge equivalent if there exists a gauge transformation G : V (L 1 ) → V (L 2 ) and we use the notation L 1 ∼ g L 2 .
Suppose L 1 ∼ g L 2 where the gauge transformation from L 1 to L 2 is a single term operator, c(x)τ n for n < ord(L 1 ). Then τ n · L 1 · τ −n is term equivalent to L 2 where the term transformation from τ n · L 1 · τ −n to L 2 is τ − c(x+1) c(x) .

How to compute the gauge transformation
Suppose L 1 and L 2 are gauge equivalent and G is a gauge transformation from L 1 to The algorithm that was used to find the gauge transformation in [4,6,29] works as follows: 1. For given operators L 1 and L 2 , we set up the ansatz G := 2. Right divide L 2 · G by L 1 and set the remainder to zero. This way we obtain a system A of difference equations for the unknown coefficients c i (x).
3. Compute the rational solutions of the system A to determine the values for the c i (x).
This algorithm was efficient for second order operators, but for operators of order three and higher, computing a solution of the system A, we get at Step 2, is very costly. Hence in the current implementation we use the new algorithm HOM to compute the gauge transformations that give the set of homomorphisms This means in particular that we can drop the condition on the orders, ord(L 1 ) = ord(L 2 ).
In short, the algorithm HOM works as follows: Then there is a one to one correspondence between Hom(L 1 , L 2 ) and rational (invariant under the difference Galois group) elements of . Then rational elements of M(L ∨ 1 , L 2 ) correspond bijectively to elements of Hom(L 1 , L 2 ). Thus, we compute rational elements of M(L ∨ 1 , L 2 ). This is done by working directly with L ∨ 1 and L 2 , and we avoid computing large operators such as the symmetric product of L ∨ 1 and L 2 (whose solution space is a homomorphic image of M(L ∨ 1 , L 2 ).) Note that if L 1 and L 2 are of the same order, then HOM returns exactly the gauge transformations. The algorithm HOM is available at http://www.risc.jku.at/people/ycha/Hom.txt and more details can be found in [5]. This is joint work of Yongjae Cha and Mark van Hoeij.

GT-equivalence Definition 2.7. Suppose there is a gauge transformation G and a term transformation
. Then L 1 and L 2 are called GT-equivalent, denoted by L 1 ∼ gt L 2 , and the composition of G and T is refered to as the GT-transformation from L 1 to L 2 .
Suppose there is a map GT which is a multiple composition of gauge transformations and term transformations. Then [19,Theorem 3.3.] shows that we can find a gauge transformation G and a term transformation T such that GT (V (L 1 )) = G • T (V (L 1 )).

How to compute the GT-Transformation
SNF(r(x)) is unique up to the choice of C. In the algorithm given in Section 5 The original statement of the above theorem uses C = C, but the same proof works for any subfield C of C.
Suppose we know that and we want to find the GT-transformation. By the above theorem there exists r( can be gauge equivalent to L 2 . Thus the algorithm Hom will return a non-empty set for either of the two. Furthermore, when d is odd, L 1 (τ − r(x)) is gauge equivalent to L 2 .

Symmetric powers of operators
Given an operator L ∈ D that annihilates a function u, then in order to obtain an operator M ∈ D that annihilates u 2 we need the symmetric square of L. In this section we state some facts about these operators.
By L m we denote the m th symmetric power of L, i.e.,we define L 1 = L and L m = L L (m−1) . K is called a symmetric square root of L if L = K 2 .
Suppose K d is a differential operator of order 2 then it is known that the order of . However the following lemma shows that this is not true for difference operators.
The formulas above give order-minimal operators for both cases.
If a full operator K = a 2 (x)τ 2 + a 1 (x)τ + a 0 (x) is a symmetric square root of a third order operator L, then also K = a 2 (x)τ 2 − a 1 (x)τ + a 0 (x) is a symmetric square root of L. If u is a solution of K, then (−1) x u is a solution of K. We say K and K are conjugates if K ∼ t K where the term transformation is τ + 1.
Solutions of an equation of type 2 are called Liouvillian solutions [4,14,29]. Sup- Also, it is easy to verify that for arbitrary orders m it holds that K m = a 2 (x) m τ 2 + (−1) m+1 a 0 (x) m with a similar proof to the one of Lemma 2.10. Definition 2.11. A second order operator K is called a unity free operator if the solution space of K does not admit a basis {v 1 , v 2 } such that v n 1 = v n 2 for some n ∈ N.
is not a unity free operator.
Lemma 2.12. If K ∈ D is an irreducible second order operator then it is a unity free operator.
Proof. We prove this by contraposition. Suppose K ∈ D is not a unity free operator. Then we may assume K is monic and V (K) admits a basis {v 1 , v 2 } such that v n 1 = v n 2 for some n ∈ Z. Let n 0 ∈ Z >0 be the smallest integer that satisfies v n0 where u n0 denotes n 0 th root of unity and n 0 , a, b are pairwise relatively prime. Thus K = (τ 2 − (u a n0 + u b n0 )τ + u a n0 u b n0 ) (τ − r) where r = τ (f )/f . Since K is an element in D and by equation (1), r is in C(x) and this implies K is reducible in D.

Lemma 2.13.
If v ∈ S, v = 0 satisfies a full second order operator Proof. We will prove that v has only finitely many zeros. Since and b i (x) has no poles or roots for all x ≥ n 0 , i = 1, 2. Suppose v(n 1 ) = v(n 1 +1) = 0 for some n 1 ≥ n 0 . Then by (2), v(x) = 0 for all x ≥ n 1 and this contradicts that v = 0.
Suppose v(n 2 ) = 0, v(n 2 + 1) = 0 for some n 2 ≥ n 0 . Then again by (2), v(x) = 0 for all x ≥ n 2 + 1. Thus v(x) = 0 for x large enough and hence v is a unit. c 0 then f (z) = 0, i.e. f (z(x)) = 0 for all x ∈ N. Thus, z(x) ∈ {c ∈ C | f (c) = 0} for all x ∈ N and v 1 = zv 2 . Suppose z is not a constant sequence. Since K is an irreducible full operator in D, it contradicts that v 1 is a solution of K. Suppose z is a constant sequence. Then it contradicts that v 1 are v 2 linearly independent.
In the differential case it holds that if the symmetric square of a third order differential operator L d ∈ C(x)[∂] has order 5, then L d = K 2 d for some second order operator K d ∈ C(x) [∂]. However, the following example shows that this does not hold in the difference case.

is not a solution of any shift operator in D, [11, Theorem 5.2]and [7, Lemma A.2], K 1 is not a symmetric product of B and a difference operator in D.
In the differential case, suppose L d ∼ t K 2 d , i.e, the solution of L d can be obtained by multiplying a hyperexponential term h to the solutions of K 2 d . Let {u 1 , u 2 } be a basis of the solution space of K d , then L d admits a basis of the solution space {gu 2 1 , gu 1 u 2 , gu 2 2 }. However, if g is hyperexponential then √ g is also hyperexponen-

However if h is a hypergeometric term,
√ h is not guaranteed to be a solution of an operator in D.

Definition 2.16.
An irreducible operator L is said to be solvable in terms of second order in D if it is GT-equivalent to K 1 K 2 · · · K d where the K i 's are irreducible and full second order operators in D.
We need the following Lemma to prove Theorem 2.18. Lemma 2.17. Let K 1 , K 2 ∈ D be full second order operators. If ord(K 1 K 2 ) = 3 then we can choose a basis {v 1 , v 2 } of V (K 1 ), and a basis Proof. Let {v 1 , v 2 } be a basis of V (L 1 ) and {w 1 , w 2 } be a basis of V (L 2 ). Since ord(K 1 K 2 ) = 3, the C-vector space generated by {v 1 w 1 , v 1 w 2 , v 2 w 1 , v 2 w 2 } has dimension 3. Then there exists a 1 , a 2 , a 3 ∈ C, which are not all zero, such that Suppose a 1 = a 2 = 0 and a 3 = 0 then it contradicts that v 1 and v 2 are linearly independent. Likewise, if a 2 = a 3 = 0 and a 1 = 0 then it contradicts that w 1 and w 2 are linearly independent. If a 1 = a 3 = 0 and a 2 = 0 then we have the desired form. So, the remaining cases are either only one of the coefficients a 1 , a 2 , a 3 is zero, or all a 1 , a 2 , a 3 are non-zero. Here, we will prove the case when a 2 is the only zero coefficient. Let {w 1 ,w 2 } be another basis of V (L 2 ) such that Then for {w 1 ,w 2 } we have v 1w2 = v 2w1 as claimed.  Proof. Let L be a third order, irreducible operator that is solvable in terms of second order in D. Then by definition (and the restriction of the order), there exist two irreducible full second order operators K 1 , K 2 ∈ D such that L ∼ gt K 1 K 2 . By Lemma 2.17, a suitable basis {v 1 , v 2 } for K 1 , and a suitable basis {w 1 , w 2 } for K 2 can be chosen, such that v 1 w 2 = v 2 w 1 . Let h = w 1 /v 1 = w 2 /v 2 , then h ∈ S and w 1 = hv 1 , and w 2 = hv 2 . Since {w 1 , w 2 } is a basis for an operator in D, h is hypergeometric and this implies that K 1 ∼ t K 2 with term transformation τ − r, where r is the certificate of the hypergeometric term h. Summarizing, by Lemma 2.10, L ∼ gt K 2 for some full operator K ∈ D.
(a) Let {v 1 , v 2 } be a basis of V (K) and τ − r be the term transformation from K 2 to L and h be a solution of τ − r. Then {hv 2 1 , hv 1 v 2 , hv 2 2 } forms a basis of L and thus ord(L 2 ) = 5 by Lemma 2.14.
Suppose L d is a differential operator of order 3 and L d = K 2 d for some second order differential operator K d . Then it is well known that there exists a formula to construct this K d , see [22,Lemma 3.4]. The case where only gauge-equivalence holds, i.e., L d ∼ g K 2 d , is more interesting. In [28] third order operators are treated with a focus on determining both K d and a gauge transformation.
It is possible to implement a similar algorithm for difference equations which returns the second order operator K to which the given L can be reduced to and a gauge transformation. However, in the difference case, in order to give a closed form solution of K other algorithms need to be applied or a table look-up. Also, even if we are in case (a), finding K is not as simple as in the differential case, in particular if there is a parameter included in the input. Morever to distinguish the cases, the symmetric square of a third order operator needs to be computed which can become costly if many parameters are involved.

Local data
The local data that we are using are the valuation growths at finite singularities in C/Z and generalized exponents at the point of infinity. This data is invariant under GT transformations. In this section, we review the definition and an invariance property (Theorem 3.6, Theorem 3.14) of local data from [3,4,6,27]. We omit proofs in this paper.

Finite singularities
Valuation growth was first introduced in [27] and an algorithm to compute it was given in the same paper. Let L = a d τ d + · · · + a 0 τ 0 ∈ D. After multiplying L from the left by a suitable element of C(x), we may assume that the a i are in C[x] and gcd(a 0 , . . . , a d ) = 1. Then q ∈ C is called a problem point of L if q is a root of the polynomial a 0 (x)a d (x − d) and p ∈ C/Z is called a finite singularity of L if L has a problem point in p (i.e. p = q + Z for some problem point q). Let p ∈ C/Z. For a, b ∈ p ⊂ C we say a > b iff a − b is a positive integer.
Let ε be a new indeterminant, i.e., transcendental over C. We define L ε := d i=0 a i (x+ ε)τ i which is obtained by substituting x with x + ε in L. The map L → L ε defines an embedding (as non-commutative rings) of We define an ord(L) dimensional C(ε)-vector space Let q l be the smallest root of a 0 (x)a d (x − d) in p, so q l is the smallest problem point in p. Likewise we define q r to be the largest root of a 0 (x)a d (x − d) in p. If p is not a singularity, that is, if a 0 and a d have no roots in p, then choose two arbitrary elements in p and define q l , q r to be those two elements.
We define v ε,l (ũ) as v q l −d q l −1 (ũ) which, by Lemma 3.3, equals the box valuation of any box on the left of q l . Likewise we define v ε,r (ũ) as v qr +1 qr +d (ũ).

Definition 3.4.
Define the valuation growth of non-zeroũ ∈ V p (L ε ) as Define the set of valuation growths of L at p as If L is a first operator operator then g p (L) has only one element.
Definition 3.5. Let L be a difference operator and p ∈ C/Z be a finite singularity of L. If g p (L) has more than one element then p is called an essential singularity.
The algorithm given in [27] determines the set {g p (L) | p is an essential singularity of L}.
The following lemma is an immediate consequence of Definition 3.4.
The above theorem only gives invariance under gauge equivalence. To have invariance under GT-equivalence, we need to define one more set. Suppose L 1 ∼ gt L 2 , then L 1 (τ − r(x)) ∼ g L 2 for some r(x) ∈ C(x). Then max(g p (L 2 )) = max(g p (L 1 )) + d and min(g p (L 2 )) = min(g p (L 1 )) + d where {d} = g p (τ − r(x)), d ∈ Z. So d p (L) = max(g p (L))− min(g p (L)) is invariant under GT-equivalence. Thus, for a difference operator L ∈, we define a set of ordered pairs ValG := {(p, d p (L)) ∈ C/Z × Z ≥0 | p is an essential singularity of L}.

Singularity at infinity
Let K := C((t)), x = 1/t be the field of formal Laurent series and K r = C((t 1/r )) for r ∈ N. We define the valuation for a ∈ K as the smallest power of a whose coefficient is non-zero and denote it by v(a). This definition can be extended toD = K[τ ] = K[∆], where ∆ := τ − 1 denotes the forward difference, by setting v(L) = min{v(a i ) + i | L = a 0 + · · · + a d ∆ d } for any operator L ∈D.
There exists a polynomial P such that for every n ∈ Z we have L(t n ) = P (n)t n+v(L) + · · · where the dots refer to terms of valuation > n + v(L). Definition 3.9. Ind L (n), the indicial polynomial of L, is the polynomial P (n) in Lemma 3.8 (3).
Lemma 9.2 in [6] states that if N ∈ Z is a root of Ind L (n) then there is u ∈ K such that L(u) = 0 and v(u) = N . However, there is no one-to-one correspondence between solutions of L in K and integer roots of Ind L (n). For this matter, we introduce the ring K[l], where l is a solution of τ (l)− l = t, see [18] for existence of l. We extend valuation on K to K[l] by: for a = a 1 t d + · · · ∈ K[l], a i ∈ C[l], d ∈ Z, and a 1 = 0, we let v(a) = d. With this notion we obtain the following theorem which is equivalent to [3, Theorem 3. with v(u) = p.
An immediate consequence of the above theorem is the following corollary. Define the action of τ on K r as: Since we have defined the action of τ on K r , we can now apply the formula for the term symmetric product in (1) to K r [τ ]. Let E r andG r be the following subset and subgroup, respectively, of K * r : Now E r is a set of representatives for K * r /G r . The composition of the natural maps K * r → K * r /G r → E r defines a natural map Definition 3.12. Let r ∈ N then for a, b ∈ E r , we say a is r-equivalent to b, a ∼ r b, when a/b ∈ G r .
Note that a ∼ r b if and only if a r ≡ b r mod 1 r Z with a r as in the definition of E r , a i = b i for i < r, and c, v matching as well.
Definition 3.13. Let g ∈ E r for some r ∈ N. We say that g is a generalized exponent of L with multiplicity m if and only if zero is a root of IndL(n) with multiplicity m whereL = L (τ − 1 g ). We denote by GenExp(L) the set of generalized exponents of L.
Theorem 3.14. If two operators L 1 and L 2 are gauge equivalent then for each g 1 ∈ GenExp(L 1 ) there is a g 2 ∈ GenExp(L 2 ) such that g 2 is equivalent to g 1 .
This theorem has been proven first in [6]. An alternative proof can be found in [3]. Likewise for the valuation growth, we need to define one more set to have invariance for GT-equivalence. Suppose L 1 (τ − r(x)) ∼ g L 2 for some r(x) ∈ C(x). Then GenExp(L 2 ) = {g r g | g ∈ GenExp(L 1 ), {g r } = GenExp(τ − r(x))}.

Table of base equations
In [3,6], we have formed a table of base equations of order 2, call it TB, as follows; • collect equations with known solution from [1,2].
• for any closed form expression that shows up often in the literature, generate a base equation with existing algorithms [8,17].
As input for our algorithm we accept only operators of order three and the above equation may be of higher order. One way of obtaining the base equation for u(x/m) in this case is using L (m) when it is a multiple of an operator M ∈ D for which M (u(x/m)) = 0. Since L (m) as constructed above is not guaranteed to be the minimial order operator we compute Hom(L (m) , L (m) ). If the algorithm HOM returns the identity map this means that L (m) is in fact order-minimal. These cases are neglected and we use L (m) as a base equation only if HOM returns a non-trivial map.
For instance for the squared hypergeometric function in the table below, , an annihilating operator L (2) can be obtained starting from an operator L (1) annihilat- ; z 2 using (5). Then the order-minimality of L (2) is checked with the algorithm HOM. In this case HOM returns a non-identity map and hence we save L (2) in the table. If . Thus, we can detect whether an input operator may have a solution u(x/m) if a base equation for u(x) is in our table. However, it is more efficient to compute the base equation for small values of m.

Algorithm
The basic structure of the algorithm is the same that was given in [3]. Here we use an extended table of base equations and a more efficient algorithm for computing the gauge transformation, as mentioned in Section 2.4.1.
Suppose L is the input operator with local data for a, b, c ∈ C. By comparing the corresponding data in TB2, we can find that local data of L matches with the data of (2) in Section 4.1. Let L lgd be the operator of which P x (z) 2 is a solution. To compute the parameter z, we compare a with each entry of Gquo(L lgd ) and compute the set of candidates of possible values for z which is, Substituting z by each of the values of the above set, a set of equations cdd2 is obtained. It remains to cheek for each of the equations in cdd2 whether there is a GTtransformation to L and if so then we return the closed form solution by applying the GT-transformation to P x (z) 2 .

Improvement
A similar approach can be applied to higher order operators that are solvable in terms of order two. Suppose L 4 is a fourth order operator that is solvable in terms of order two in D. Then L 4 is equal or gauge equivalent to either K 3 1 or K 1 K 2 for some second order operators K 1 , K 2 ∈ D with nonvanishing coefficients. The candidates for K i can be detected analogously using Theorem 3.15.
Concerning the applications to proving positivity of special functions inequalities it has to be noted that representations in terms of finite linear combination of squares with non-negative coefficients need not exist on the full range of validity of a given inequality, as can be seen below. Further investigations of the applicability of this approach as well as an implementation of the above mentioned extension to higher order recurrences are ongoing work.

Applications
Our main motivation to extend finding closed form solutions of difference equations in terms of symmetric products is to develop an algorithmic approach for proving special functions inequalities. Existing symbolic methods [12,15,16] are based on using Cylindrical Algebraic Decomposition (CAD) which in several examples has proven to be an effective way for proving positivity of sequences that are given only in terms of their defining sequences. However, it is sometimes unsatisfiable to have a proof that only comes with "True" without any certificate. Some classical proofs of inequalities are using rewriting of the given expression as linear combination of easy to verify positive objects such as sums of squares. The present work tries to make this approach algorithmic. Certainly it will not provide answers for any special functions inequality, but it is a first step in a new direction of automatic inequality proving. Below we give two examples, one for each of the cases distinguished above, of classical problems that can be solved fully or at least partially using the presented algorithm. Note that all of these identities stated can be proven easily using existing algorithms for symbolic summation. The novelty is the automatic discovery of certain closed form expressions for sequences that are given only in terms of their defining recurrence relation. In this sense it is comparable to the above mentioned algorithms based on CAD.

Clausen's formula
Proofs of special function inequalities often depend on a variety of classical techniques such as argument transformations, integral representations of hypergeometric series and many more. For instance in the proof of the Askey-Gasper inequality [2],which played a key role in the proof of the Bieberbach conjecture by de Branges [9], Clausen's formula 3 F 2 −x, x + α + 1, α+1 2 α + 1, α+2 2 ; z (6) ; z 2 entered at a central point. Zeilberger [10] has shown how this identity can be proven using symbolic summation. By means of the algorithm presented here, Clausen's formula can be discovered entirely automatic. The hypergeometric function in (6) satisfies a third order recurrence that is given by the operator L 3 and is too large to be displayed here. It can however be found easily common symbolic summation algorithms [30,8,17]. This difference operator is the input for our procedure and we start by determining the local data given by A table look-up shows that this local data is compatible with 1 in Section 4.1. Comparing local data and solving the system mod Z the following candidates for a, b and c can be found: a ∈ {0, 1 2 }, b ∈ { 1 2 α, 1 2 α + 1 2 }, c ∈ { 1 2 α + 1, 1 2 α + 3 2 }.
There is no term transformation for these operators and an application of HOM shows that we obtain a constant map if a = 0, b = 1 2 α + 1 2 and c = 1 2 α + 1.

Turán inequality for Hermite polynomials
The positivity of Turán determinants has been proven for many different families of orthogonal polynomials. The first Turán inequality was formulated for Legendre polynomials [25] and Szegö [23] has given four different proofs of this inequality. Szwarc [24] has provided a more general approach for proving Turán type inequalities based on the mere knowledge of the recurrence coefficients satisfied by the given sequence. Gerhold and Kauers [13] have proven and improved this type of inequalities using their CAD-based method. The approach presented here does not give a full proof for Turán type inequalities, however it gives a representation of the given determinant in sums of squares derived from the third order annihilating operator of the determinant. In the case of Hermite polynomials this yields a representation that gives positivity in the limit for n tending to infinity. Turán's inequality for Hermite polynomials H x (z) reads as follows: Then an annihilating operator of ∆ x (z) is L h := τ 3 + (2x + 2 − 4z 2 )τ 2 − 4(x + 2)(x − 2z 2 + 4)τ − 8(1 + x)(x + 2) 2 and the local data of this operator is ValG(L h ) = {(0, 2)} .
−1 ± √ −2 z 2 t 1 2 + z 2 ± 1 t are elements in Gquo(L h ) and these are equivalent to −1 ± √ −2 z 2 t 1 2 + z 2 t under ∼ 2 , see Definition 3.12 for ∼ 2 . Thus the local data of L h correspond to those of the third entry of the table given in Section 4.1.
Using the algorithm described above a gauge transformation can be found that applied to H x (z) 2 yields the following equivalent formulation This representation gives the positivity of Turán's inequality for