% From abramov@ccas.ru Mon Nov 23 05:09:05 1998 % Return-Path: % Received: from ccas.ru (ext1.ccas.ru [193.233.208.3]) % by lars.math.fsu.edu (8.8.7/8.8.7) with ESMTP id FAA06397 % for ; Mon, 23 Nov 1998 05:09:01 -0500 % (EST) % Received: from mirror.ccas.ru (mirror.ccas.ru [193.232.81.31]) by % ccas.ru % (8.7.5/8.7.3) with SMTP id NAA08521 for ; Mon, % 23 Nov 1998 13:03:02 +0200 (EET) % Date: Mon, 23 Nov 1998 13:03:02 +0200 (EET) % From: "Sergei A. Abramov" % Message-Id: <199811231103.NAA08521@ccas.ru> % To: hoeij@lars.math.fsu.edu % Subject: final version % Status: OR \documentstyle[fullpage]{article} \newcommand{\dA}{d'Alembert} \newcommand{\by}[2]{#1 (#2):} \newcommand{\paper}[1]{#1} \newcommand{\journal}[2]{{\em #1\/}~{\bf #2}} \newcommand{\pages}[2]{#1--#2} \newcommand{\book}[1]{{\em #1\/}} \newcommand{\bookinfo}[1]{#1} \newcommand{\publisher}[1]{#1} \newcommand{\inbook}[2]{in: (#1) {\em #2\/}} \newcommand{\al}{{\cal A}_k} \newcommand{\h}{{\cal H}_k} \newcommand{\ord}{{\rm ord}\,} \newcommand{\Ker}{\hbox{Ker}\,} \newcommand{\W}{{\rm W}} \newcommand{\st}{\mbox{ such that }} \newcommand{\ie}{{\it i.e.~}} \newcommand{\qed}{\hfill$\Box$\par\medskip} \newcommand{\qee}{\hfill$\Box$} \newcommand{\nozero}{\setminus\{0\}} \newcommand{\th}[1]{#1^{{\rm th}}} \newcommand{\ore}{k[X;\sigma,\delta]} \newcommand{\dt}{\sigma =1} \newcommand{\s}{\sigma } \newcommand{\n}{\Delta } \newcommand{\dc}{\sigma \neq 1} \newcommand{\rop}{k[\theta]} \def\sgn{{\rm sgn\,}} \def\o{\circ} \def\wt{\widetilde} \def\ord{{\rm ord\,}} \def\ad{{\rm ad\,}} \def\ns{{\rm I\!N}} \def\zs{{\rm Z\!\!Z}} \def\rs{{\rm I\!R}} \def\cs{ \hbox{\raise.46ex\hbox{$\scriptscriptstyle |$}\kern-.36em\hbox{\rm C}}} \def\qs{ \hbox{\raise.49ex\hbox{$\scriptscriptstyle |$}\kern-.33em\hbox{\rm Q}}} \tolerance=10000 \newtheorem{Theorem}{Theorem} \newtheorem{Proposition}{Proposition} \newtheorem{Corollary}{Corollary} \newtheorem{Lemma}{Lemma} \newtheorem{Definition}{Definition} \newtheorem{Example}{Example} \newtheorem{Remark}{Remark} \begin{document} \title{\Large\bf Integration of Solutions of Linear Functional Equations} \author{\large\sl Sergei A.~Abramov\thanks{Supported in part by the RFBR and INTAS under Grant 95-IN-RU-412 and by RFBR under Grant 98-01-00860. } \\ \normalsize Computer Center of\\ \normalsize the Russian Academy of Science, \\ \normalsize Vavilova 40, Moscow 117967, \normalsize Russia \\ \normalsize {\tt abramov@ccas.ru}\\ \normalsize {\tt sabramov@cs.msu.su} \and \large\sl Mark van Hoeij \\ \normalsize Department of mathematics \\ \normalsize Florida State University,\\ \normalsize Tallahassee, FL 32306-3027, USA\\ \normalsize {\tt hoeij@math.fsu.edu}} \date{} \maketitle \begin{abstract} We introduce the notion of the adjoint Ore ring and give a definition of adjoint polynomial, operator and equation. We apply this for integrating solutions of Ore equations. \end{abstract} \section{Introduction} \noindent The goal of this paper is integration (in the difference case: summation) of solutions of Ore equations. For this purpose we first define an adjoint for an Ore ring, similar to the well-known adjoint for differential operators, and also similar to ideas in \cite{Cohn}. The use of Ore rings allows to handle the case of differential, difference and q-difference equations simultaneously. An application is integration of special functions, like Bessel functions or hypergeometric functions. If a function satisfies a differential operator $L$ for which the operator $\tilde{L}$ that we will compute has the same order then we have an easy way to integrate. This will be illustrated with an example. The integrals of special functions that we obtain this way are often much less complicated than the integrals given by computer algebra systems. Another situation where solutions of linear differential equations need to be integrated is the following. For solving linear differential equations one often applies ``reduction of order'' in case one of the solutions was found. Reduction of order leads to the problem of integrating solutions of a differential equation. In this paper we give a simple and easy to implement method for this problem. Given an operator $L$, our algorithm computes an operator $\tilde{L}$ of minimal order such that the derivatives of the solutions of $\tilde{L}$ are the solutions of $L$. In the case that the order of $\tilde{L}$ equals the order of $L$, this effectively removes, at low computational cost, one integration symbol from the symbolic solutions of the original differential equation. The use of Ore rings makes our algorithm more general, so that it can be applied to the cases of difference and $q$-difference equations as well. A preliminary version of this paper appeared as \cite{avh}. \section{Integrating factors and adjoints} Let $k$ be a field and let $K$ be a ring that contains $k$. We consider Ore rings $k[\Delta]$ and $K[\Delta]$ for two different types of $\Delta$: \begin{itemize} \item Case 1: $\Delta$ is a derivation on $K$, i.e. $\Delta(ab) = b \Delta(a) + a \Delta(b)$ for all $a,b \in K$, and it is also a derivation on $k$ (so $\Delta(a) \in k$ for $a \in k$). \item Case 2: $\Delta=\sigma - 1$ where $\sigma$ is an automorphism of $k$ and of $K$. \end{itemize} In both cases we will assume that the set of constants ${\rm Const} = \{a \in K| \Delta(a) = 0\}$ is a subfield of $k$. Let $k[\Delta]$ be the ring of all operators $\sum_{i=0}^n a_i \Delta^i$. Similarly define $K[\Delta]$. An element operator $L \in K[\Delta]$ can be viewed as a ${\rm Const}$-linear map from $K$ to $K$, $L(y)=\sum_{i=0}^n a_i \Delta^i(y) \in K$. We will assume that $\sum a_i \Delta^i \in K[\Delta]$ acts as the zero map on $K$ if and only if all $a_i$ are zero. A common situation for such Ore rings is that one is given an equation $L(y)=0$ for some $L \in k[\Delta]$ and one is interested in finding solutions $y$ of this equation in some (field or ring) extension $K$ of $k$. By ``rational solutions'' of $L$ we mean solutions $y \in k$. Now $k[\Delta]$ and $K[\Delta]$ are rings. The multiplication in these rings corresponds to composition of operators. Using the relation \begin{itemize} \item Case 1: $\Delta \o a = a\Delta + \Delta(a)$ \item Case 2: $\Delta \o a = \sigma(a)\Delta + \Delta(a)$ \end{itemize} any product of elements in $K[\Delta]$ can be written in a standard form $\sum_{i=0}^n a_i \Delta^i$. We define $\Delta^*$ as follows: \begin{itemize} \item Case 1: $\Delta^*=-\Delta$ \item Case 2: $\Delta^*=\sigma^{-1}-1$ \end{itemize} and we can define the {\em adjoint ring} of $k[\Delta]$ as $k[\Delta^*]$. Note that in case 1 we have $k[\Delta] = k[\Delta^*]$ but in case 2 $k[\Delta]$ needs not be equal to its adjoint ring. Now we can define the adjoint map from \[ {\rm ad}: \ k[\Delta] \rightarrow k[\Delta^*] \] for an operator $L=\sum_i a_i \Delta^i$ as follows: \[ {\rm ad} \ L = \sum_i (\Delta^*)^i \o a_i. \] This can be rewritten to the standard form ${\rm ad} \ L = \sum_i b_i (\Delta^*)^i$ for some $b_i \in k$. For brevity we will often write $L^*$ instead of ${\rm ad} \ L$. Now one can verify that the adjoint is a ${\rm Const}$-linear bijective map and that \[ (L \o M)^* = M^* \o L^* \] for all $L,M \in k[\Delta]$. \begin{Proposition} \label{propo_Delta} $$ \Delta(f)=0 \Longleftrightarrow f \in {\rm Const} \Longleftrightarrow \Delta^*(f)=0. $$ Additionally for any $L \in K[\Delta]$ $$ L(1)=0 \Longleftrightarrow \exists_{M} \ L = M \o \Delta$$ and $$ L^*(1)=0 \Longleftrightarrow \exists_{M} \ L = \Delta \o M.$$ \end{Proposition} \noindent {\em Proof:\/} The first statement follows from the definitions. Write $L=\sum_i a_i \Delta^i$ for some $a_i \in K$. Now $L=M \o \Delta$ for some $M$ if and only if $a_0=0$. Now the second statement follows because $a_0=L(1)$. For the third statement, write $L^* \in K[\Delta^*]$ (note that in general $L^*$ needs not be an element of $K[\Delta]$) as $L^*=\sum_i a_i(\Delta^*)^i$ % = \sum_i (\Delta^*)^i b_i$ for some $a_i,b_i \in K$. for some $a_i \in K$. Now $L=\sum_i \Delta^i a_i$ % (this can be rewritten as $\sum_i b_i \Delta^i$ for some $b_i \in K$) and $L=\Delta \o M$ for some $M$ iff $a_0=L^*(1)=0$. \qed %%% For the second statement, if $L = M \o \Delta$ then $L(1)=M(\Delta(1))=M(0)=0$. %%% Conversely, if $L(1)=0$ then %$L$ %and $\Delta$ have a common solution. So %$L$ and $\Delta$ have a non-trivial greatest common right divisor. %Because $\ord \Delta = 1$ %%% this is only possible if $\Delta$ is %%% a right hand factor of $L$. %%% MVH: that's not a proof. %If $L^*$ and $\Delta^*$ have a common non-zero solution then %$L^*$ and $\Delta^*$ have a non-trivial greatest common right %divisor and %hence $L$ and $\Delta$ have %a non-trivial greatest common left divisor. Now %%% The third statement follows in the same way %%% as the second statement. \qed An element $l\in K$ is an {\em integrating factor} for $L\in K[\Delta] $ if $lL=\Delta \o M$, for some $M\in K[\Delta ]$. The following proposition shows that in the general case the adjoint equation has an important feature which is well-known in the differential case. \begin{Proposition} \label{prop_int} $l\in K$ is an integrating factor for $L$ iff $L^*(l)=0$. \end{Proposition} \noindent {\em Proof:\/} By proposition~\ref{propo_Delta} we have $lL=\Delta \o M$ for some $M$ iff $(lL)^*(1)=0$. Since $l \in K$ we have $l^*(1)=l(1)=l$ and so $(lL)^*(1)=L^*(l)$. \qed \section{Accurate integration} %%Let $K$ be again a $\sigma, \delta$-compatible %%%field %%ring extension of $k$. An element $g\in K$ is a {\em primitive} of $f\in K$ if $\Delta(g) = f$. % We assumed that $c\in k$ (it implies that $\Delta \in k[\Delta]$) and Consider the following problem: {\em Let\/} $f \in K$ {\em and the minimal annihilating operator\/} $L\in k[\Delta]$ {\em for $f$ be given. So $n=\ord L$ is minimal with the property that $L \in k[\Delta]$ and $L(f)=0$. Decide whether there exists a primitive $g$ of \/} $f$ {\em such that the minimal annihilating operator \/} ${\wt L}$ {\em for\/} $g$ {\em has order\/} $n$. {\em If so, then construct all such\/} $g$ {\em together with their minimal annihilating operators}. \noindent We show that this problem (the problem of the {\em accurate integration}) can be solved with the help of finding integrating factors. Let $g$ be any primitive of $f$ and ${\wt L}\in k[\Delta] $ be the minimal annihilating operator for $g$. Now $L\o \Delta(g)=L(f)=0$ hence by the minimality of ${\wt L}$ (and by the fact that $k[\Delta]$ is a Euclidean ring, c.f.\ \cite{O}) it follows that ${\wt L}$ is a right-hand factor of $L\o \Delta$. Hence \[ \ord {\wt L}\leq \ord { L\o \Delta } = n+1 {\rm \ and \ if \ } \ord {\wt L} = n+1 {\rm \ then \ } {\wt L} = L\o \Delta. \] Consider the least common left multiple ($LCLM$) of ${\wt L}$ and $\Delta $ presented in the form \begin{equation} \label{eq:6.} LCLM({\wt L},\Delta )=L_1\o \Delta , \end{equation} $L_1 \in k[\Delta], \ord L_1 \leq \ord {\wt L}$. We have ${\wt L}(g)=0$, so $L_1 \o \Delta (g)=0$, hence $L_1(f)=0$ and so $\ord L_1 \geq n$ by the minimality of $L$. So $\ord LCLM({\wt L},\Delta ) \geq n+1$ and hence \begin{equation} \label{GCRD} \ord{\wt L} \geq n \ \ {\rm and \ \ if \ \ } \ord{\wt L} =n {\rm \ \ then \ \ } GCRD({\wt L},\Delta)=1 \end{equation} where $GCRD$ stands for greatest common right divisor. Thus there are two alternatives for $\ord {\wt L}$: $n$ or $n+1$. The questions are: when is $\ord {\wt L}=n$ and what is ${\wt L}$ in this case? If $\ord {\wt L}=n$ then from equation~(\ref{GCRD}) and the extended Euclidean algorithm it follows that \begin{equation} \label{eq:9.} r\o \Delta + {\wt l}\o {\wt L}=1 \end{equation} for some ${\wt l},r\in k[\Delta]$ with $\ord r < \ord {\wt L} = n$ and $\ord {\wt l} < \ord \Delta = 1$. Applying equation~(\ref{eq:9.}) on $g$ results in \[ r(f)=g. \] Applying $\Delta$ on this equation yields $\Delta \o r (f)=f$ so $(1-\Delta \o r)(f)=0$. By the minimality of $L$ it follows that $1-\Delta \o r = l \o L$ for some operator $l$; hence \begin{equation} \label{eq:8.} \Delta \o r + l\o L=1. \end{equation} Conversely, if equations~(\ref{eq:9.}),(\ref{eq:8.}), $\ord r < n$ and $\ord {\wt l}<1$ hold then one can easily verify that $\ord {\wt L}=n$, that ${\wt L}$ is the minimal annihilating operator for $r(f)$ and that $\Delta(r(f))=f$. Hence equations~(\ref{eq:9.}),(\ref{eq:8.}) with the conditions on $\ord r$ and $\ord {\wt l}$ are equivalent to the problem of accurate integration. The inequality $\ord {\wt l} < 1$ implies $\ord l =\ord {\wt l}=0$, i.e. $l,{\wt l}\in k$. Both sides of (\ref{eq:8.}) are operators and if we take the adjoints we get \begin{equation} \label{eq:10.} r^* \o \Delta^* + L^* \o l^*=1. \end{equation} Applying the left- and the right-hand sides of (\ref{eq:10.}) to the constant function 1 we obtain \begin{equation} \label{eq:11.} L^* (l)=1. \end{equation} For each solution $l \in k$ of~(\ref{eq:11.}) we have $(1-lL)^*(1)=1-L^*(l)=0$ and so by proposition~\ref{propo_Delta} it follows that equation~(\ref{eq:8.}) allows a unique solution $r$. The minimal annihilating operator of $g$ is defined up to a left-hand factor in $k$. Therefore we can take ${\wt l}=1$ and \begin{equation} \label{eq:14.} {\wt L}=1-r\o \Delta . \end{equation} This operator annihilates one-unique primitive $r(f)$ of $f$. If operators $r_0$ and $r_1$ correspond to different solutions $l_0$ and $l_1$ of (\ref{eq:11.}) then the primitives $r_0(f)$ and $r_1(f)$ of $f$ are also different (otherwise the operator $r_0-r_1$ of order $< n$ annihilates $f$). Since primitives are determined up to constants it follows that $(r_0-r_1)(f)$ must be a constant. ${\wt L}$ maps the primitive $r(f)$ of $f$ to 0. Furthermore it maps any constant to itself. Hence it maps any primitive of $f$ to a constant. The preceding can be formulated as the following \begin{Proposition} \label{propo_5} Let $L \in k[\Delta]$ be the minimal annihilating operator for $f\in K$ and $L^*(l)=1,\/l\in k$. Then the equality $\Delta \o r + l\o L=1$ uniquely determines $r$. In turns $r$ lets find the operator ${\wt L} \in k[\Delta]$ (up to a factor in $k$) annihilating the primitive \begin{equation} \label{eq:prim} g=r(f) \end{equation} of $f$. If formula (\ref{eq:14.}) is used to construct ${\wt L}$ then ${\wt L}(g_1) \in {\rm Const}$ for any primitive $g_1$ of $f$. \qed \end{Proposition} If (\ref{eq:11.}) has no solution in $k$ then no primitive of $f$ has a minimal annihilating operator over $k$ of order $n$. If (\ref{eq:11.}) has a unique solution in $k$ then a primitive and its minimal annihilating operator can be defined uniquely by (\ref{eq:prim}),(\ref{eq:14.}). \begin{Proposition} Let ${\cal M}$ be the set of all solutions of (\ref{eq:11.}) in $k$. Then ${\cal M}$ is empty, or ${\cal M}$ has only one element, or ${\cal M}$ has the form \begin{equation} \label{eq:15.} {\cal M} = \{l_0+Ch | C \in {\rm Const} \} \end{equation} where $l_0,h \in k$, $h\neq 0$. In the last case any primitive of $f$ has a minimal annihilating operator of order $n$. \end{Proposition} \noindent {\em Proof:\/} Suppose there exists a solution $l_0$ of~(\ref{eq:11.}). Then the solution space of~(\ref{eq:11.}) is of the form $l_0 + V$ where $V$ is the solution space of $L^*(l)=0$. The map $l \mapsto r(f)$ ($r$ depends on $l$ by~(\ref{eq:8.})) is an injective (here we use that $L$ is minimal) linear map from $l_0 + V$ to the set of primitives of $f$. Since the set of primitives is an affine space of dimension 1, $V$ must have dimension $\leq 1$. \qed Note that if the solution space of $L^*(l)=0$ has dimension $>1$ then the map $l \mapsto r(f)$ can not be injective because the image of this map has dimension $\leq 1$. The fact that the map is not injective means that there exists an $r$, $\ord r < \ord L$, with $r(f)=0$ which contradicts our assumption that $L$ is minimal. Let now ${\cal M}$ have the form (\ref{eq:15.}). Denote by $l_C$ the solution $l_0+Ch$ of (\ref{eq:11.}) and by $r_C$ and ${\wt L}_C$ the operators which are found starting with $l_C$. Since $h$ is an integrating factor for $L$ we have $hL= \n \o M,\/ \ord M=n-1$. Now from (\ref{eq:8.}) and (\ref{eq:14.}) we obtain \begin{equation} \label{eq:17,.} r_C= r_0-CM \end{equation} \begin{equation} \label{eq:17.} {\wt L}_C= {\wt L}_0+CM\o \n \end{equation} where $r_0$ and ${\wt L}_0$ correspond to the solution $l_0$ of (\ref{eq:11.}). The operator ${\wt L}_C$ is the minimal annihilating operator for the primitive \begin{equation} \label{eq:primc} g_C= r_C(f) \end{equation} of $f$. Let $g$ be a primitive of $f$ and $C\in {\rm Const}$. Then ${\wt L}_C(g)={\wt L}_0(g)+CM(\n g) ={\wt L}_0(g)+CM(f)$ and $M(\n g) \in {\rm Const}$ because $\;{\wt L}_C(g),{\wt L}_0(g) \in {\rm Const}$. Additionally $M(f) \neq 0$ because $\ord M < \ord L$. Taking \begin{equation} \label{eq:c} C= -\frac{{\wt L}_0(g)}{M(f)} \end{equation} we obtain the value of $C$ such that $g=r_C(f)$. The price which we pay for solving the problem of the accurate integration is finding solutions in $k$ of the equation $L^*(y)=1$. If $k$ is the rational function field, then the last problem can be solved effectively in all cases mentioned in the examples below (c.f.\ \cite{A89,Akva,Aprog}). % Proposition~\ref{propo_5} leads to the following algorithm. An implementation called {\tt integrate\_sols} is available in the DEtools package in Maple V release 5. As one can see below the algorithm is very short and easy to implement. \begin{tabbing} abcd \= abcd \= \kill \\ {\bf Procedure} IntegrateSolutions \\ {\bf Input:} $L \in k[\Delta]$ \\ \> $L^*$\ :=\ adjoint($L$) \\ \> Compute the rational solutions of $L^*(y)=1$ \\ \> {\bf if} there exists a rational solution {\bf then} \\ \> \> Let $l$ be a rational solution. \\ \> \> $r$\ :=\ LeftQuotient($1-l L$, $\Delta$) \\ \> \> $\tilde{L}$\ :=\ $1-r\o \Delta$ \\ \> {\bf else} \\ \> \> $\tilde{L}$\ :=\ $L \o \Delta$ \\ \> \> The integration operator $r$ does not exist. \\ \> {\bf end if} \\ {\bf Output:} $\tilde{L}$ and, if it exists, $r$ as well. \end{tabbing} \section{Examples} {\bf Example 1}. Let $k={\bf C}(x), \Delta =D=\frac d{dx}$. Applying the described approach to $f=\ln x,$ \begin{equation} \label{eq:ln} L=xD^2+D \end{equation} gives $L^*=xD^2+D$, and the general rational solution of the equation $L^*(y)=1$ is $l_C = x+C$. Therefore $l_0=x,\,h=1$. Any primitive of $\ln x$ is annihilated by a second order operator. We obtain $${\wt L}_C=(x^2+Cx)D^2-xD+1,\,r_C=(-x^2-Cx)D+x.$$ It obviously holds for any function $f(x)$ whose minimal annihilating operator has the form (\ref{eq:ln}). For $f(x)= \ln x$ we have $r_C(f(x))= x \ln x - x-C$. \\ \\ {\bf Example 2}. The algorithm proposed above lets in some cases integrate special functions. a) The minimal annihilating operator for Bessel function $J_1$ is $x^2D^2+xD+(x^2-1)$. Now $L^*=x^2D^2+3xD+x^2$, and $L^*(y)=1$ has a unique rational solution $\frac 1 {x^2}$. We obtain $${\wt L}=D^2+\frac1x D+1, \ \ \ r=-D-\frac 1 x.$$ Thus we get a primitive of $J_1$ in the form $$r(J_1)=(-D-\frac 1 x)(J_1),$$ with minimal annihilating operator ${\wt L}$. Other primitives ($r(J_1)$ plus a constant) are annihilated by the operator $L \o D$ of order 3. % This result is in agreement with the Bessel function theory. b) Another example of integration of special functions is the following: $L=xD^2+(C_1+C_2 x) D+C_3$. The solutions of this operator $L$ can be expressed in terms of Whittaker functions. Our algorithm produces the operator \[ r=\frac{x}{C_2-C_3}D+\frac{C_1+C_2x-1}{C_2-C_3}, \] so the solutions $y$ of $L$ can be integrated by our method $\int y \ dx=r(y)$. \\ \\ {\bf Example 3}. Let $k={\bf Q}(n)$, $\Delta=E-1$ where $E(n)=n+1$, $E^*=E^{-1}$. Let $u_0,u_1,...$ be Fibonacci numbers. Apply the described approach to $u_n^2,\,L=E^3-2E^2-2E+1$. We obtain $L^*=E^{-3}-2E^{-2}-2E^{-1}+1$ (note that $E=\Delta +1$ and therefore $E^*=\Delta ^*+1=E^{-1}-1+1=E^{-1}$, it lets one work with linear operators described in terms of $E$. In general in case 2 one can consider operators from $k[\sigma ]$, setting $\sigma ^*=\sigma ^{-1}$). The equation $L^*(y)=1$ has the unique rational solution $-\frac 1 2$. It shows that one unique primitive of $u_n^2$ can be annihilated by an operator of order 3: ${\wt L}=-\frac12 L$, while $r=\frac 1 2(E^2-E-3)$. This primitive is $$\frac 1 2(u_{n+2}^2-u_{n+1}^2-3 u_{n}^2).$$ The inverse of $\Delta$ is the summation operator $\sum_{i=0}^{n-1}$, up to a constant which is $\frac 1 2(u_{2}^2-u_{1}^2-3 u_{0}^2)=0$ in this example. So $$\sum_{i=0}^{n-1} u_i^2 =\frac 1 2(u_{n+2}^2-u_{n+1}^2-3 u_{n}^2).$$ There are several methods for proving such formulas. Our algorithm does more in this example, it also {\em finds} this formula. Certainly, we need the minimal annihilator for $u_{n}^2$. Since $u_{n}^2$ is a d'Alembertian sequence this annihilator can easily be constructed, for example, by algorithm \cite{AZ}. Remark that algorithm \cite{AZ} itself uses the accurate integrating algorithm. \\ \\ % Integration of algebraic functions. {\bf Example 4}. This is an example of integration of algebraic functions. If the minimal polynomial $f(x,y)\in {\bf C}(x)[y]$ for an algebraic function $\alpha (x)$ is given then the minimal annihilating differential operator $L \in {\bf C}(x)[D]$ for $\alpha (x)$ can be constructed as follows. The algebraic function $\alpha (x)$ and its derivatives are elements of ${\bf C}(x,\alpha )$, which is a ${\bf C}(x)$-vector space of dimension $\deg _y f(x,y)$. One can compute $\alpha (x), \alpha '(x), \alpha ''(x), \dots $ in this vector space. Take $\rho $ the minimal integer such that $\alpha (x), \alpha '(x), \alpha ''(x), \dots , \alpha ^{(\rho )} (x)$ are ${\bf C}(x)$-linearly dependent. This linear relation gives $L$. Now again $k={\bf C}(x), \Delta =D=\frac d {dx}$. Let $f(x,y)=y^3+xy+x^2$ and let $\alpha \in \overline{k}$ be a root of $f(x,y)$ as a polynomial in $y$. One obtains the following annihilating operator for $\alpha$ \[ L= D^2 -2\frac{1}{x(4+27x)} D +2\frac{3x+1}{x^2(4+27x)} \in k[D] \] The equation $L^*(l)=1$ has a unique rational solution $-1/45-x/12+(9x^2)/20$. This yields \[ r= (\frac1{45}+\frac{x}{12}-\frac {9x^2}{20})D +\frac{162x^2-9x-2}{180x} \] and so \[ \int \alpha \ dx = r(\alpha) = (\frac1{45}+\frac{x}{12}-\frac {9x^2}{20}) \alpha ' +\frac{162x^2-9x-2}{180x} \alpha. \] We obtain a unique primitive, despite the fact that primitives are not unique, but only unique up to a constant. Note that our method produces a primitive of $\alpha$ if and only if there is a primitive which is a $k$-linear combination of $\alpha$ and its derivatives. So in the hardest case in elementary integration (the case when logarithmic extensions are needed) our algorithm will not produce a primitive (so then ${\wt L}$ must be $L\o D$). \\[10pt] % Bad cases. {\bf Example 5}. Let $k={\bf C}(x)$ and $v(x)=1/x$. The minimal annihilating differential operator $L$ over $k$ for $v(x)$ is $L=xD+1$. The equation $L^*(l)=1$ has no solutions in $k$. So every primitive of $1/x$ is only annihilated by operators of order $\geq 2$. The primitives can not be obtained by applying linear differential operators over $k$ to $v(x)$. \\[10pt] % It is easy to construct similar examples for the difference and % $q$-difference cases: we can take $\{ n! \}\;L=nE-(n+1)$, and $\{ % xq^n \},\;L=Q-q$. {\bf Example 6}. % The algorithm described in the previous Section % is a generalization of Given a first order (i.e. hypergeometric) sequence over ${\bf C}(n)$, the well-known Gosper's algorithm (\cite{Gos}) decides whether there exists another sequence of such a kind that is a primitive for the given sequence. The algorithm in this paper generalizes Gosper's algorithm in two ways: it solves the analogous problem for a wider class of equations, and for any order $n$ instead of only $n=1$. Using (\ref{eq:prim}) we can express the mentioned primitive explicitly in terms of the given sequence (function). We will illustrate this in the difference and $q$-difference cases. %The $q$-difference case works in the same way. a) Hypergeometric case. Let $k={\bf Q}(n)$, $\Delta=E-1$. Let $s_n= {2n \choose n}/4^n, n=0,1,\dots $ This sequence is hypergeometric; $s_{n+1}/s_n=(2n+1)/(2n+2)$. We have $L=2(n+1)E-(2n+1)$. We obtain $L^*=2nE^{-1}-(2n+1)$, and the equation $L^*(y)=1$ has the unique rational solution $-1$. It shows that one-unique primitive of $s_n$ can be annihilated by an operator of order 1, and $r=2n$. This primitive is $$ 2ns_n= \frac{2n {2n \choose n}}{4^n} $$ and in particular % (take ${2n \choose n}=1$ if $n=0$) $$\sum_{n=0}^{N-1} \frac{{2n \choose n}}{4^n}= \frac{2N{2N \choose N}}{4^N}. $$ b) $q$-Hypergeometric case. Let $q$ be a new variable. A sequence $\{ h_n \}$ is $q$-hypergeometric if $h_{n+1}/h_n$ is a rational function of $q,q^n$. The sequence $$ (a;q)_n =\left\{ \begin{array}{ll} 1,& {\rm if\ }n=0,\\ (1-a)(1-aq)\cdots (1-aq^{n-1}),& {\rm if\ }n>0,\\ \end{array} \right. $$ where $a$ is a parameter is a $q$-hypergeometric for any fixed value of $a$ due to $(a;q)_{n+1}/(a;q)_n =1-aq^{n-1}= 1-a\frac {q^n}q$. We will consider the sequence $h_n=q^n(q;q)_n$. Here $h_{n+1}/h_n=q(1-q\cdot q^n)$. Write $x$ for $q^n$. Then $h_{n+1}/h_n=q(1-qx)$. Let $k={\bf Q}(q)(x)$, $\Delta=Q-1$ where $Q(x)=qx$, $Q^*=Q^{-1}$. We have $L=Q-q(1-qx)$. We obtain $L^*=Q^{-1}-q(1-qx)$, and the equation $L^*(y)=1$ has the unique rational solution $1/(q^2x)$. It shows that one-unique primitive of $h_n$ can be annihilated by an operator of order 1, and $r=-1/(qx)$. This primitive is $$ -\frac 1 {q\cdot q^n}h_n= -\frac{(q;q)_n}q $$ and in particular $$\sum_{n=0}^{N-1} q^n(q;q)_n= \frac{1-(q;q)_{N}}q. $$ Another way to obtain the last formula was demonstrated in \cite{APP}. \section{Conclusion} It follows from the results in this paper that the following 3 problems are equivalent. \begin{itemize} \item Find the solutions $l \in k$ of $L^*(l)=1$. \item Let $f \in K$. Let the minimal annihilating operator $L\in k[\Delta]$ for $f$ be given. Decide whether there exists $r \in k[\Delta]$ such that $r(f)$ is a primitive of $f$. If so, then construct such $r$. \item The problem of accurate integration. \item Computing solutions $(r,l)$ of equation~(\ref{eq:8.}). Note that according to section~3.1 in \cite{issac96} this is equivalent to computing a complement of ${\rm Const}$ in the solution space of $L \o \Delta$. \end{itemize} Similar problems, but in a more general situation, are studied in \cite{Ch,ChS}. Our approach is less general but it has the advantage of simplicity, it only uses an adjoint and rational solutions, which are quite efficient. \section *{Acknowledgement} We would like to thank Marko Petkov\v sek who provided us with useful comments on an earlier draft. \begin{thebibliography}{99} \bibitem{A89} S.~A.~Abramov (1989): Rational solutions of li\-near dif\-fe\-ren\-ce and dif\-fe\-ren\-tial eq\-ua\-ti\-ons with polynomial coefficients, {\em USSR Comput.\ Maths.\ Math.\ Phys.} {\bf 29}, 7 -- 12. Transl.\ from {\em Zl.\ Vychislit.\ matem.\ mat.\ fiz.} {\bf 29}, 1611 -- 1620. \bibitem{Akva} S.~A.~Abramov, K.~Yu.~Kvashenko (1991): Fast algorithm to search for the ra\-tional solutions of linear differential equations, {\em Proc.\ ISSAC'91}, 267 -- 270. \bibitem{Aprog} S.~A.~Abramov (1995): Rational solutions of li\-near dif\-fe\-ren\-ce and $q$-dif\-fe\-ren\-ce eq\-ua\-ti\-ons with polynomial coefficients, {\em Programming and Comput.\ Software\/} {\bf 21}, No 6, 273 -- 278. Transl.\ from {\em Programmirovanie}, No 6, 3 -- 11. \bibitem{avh} S.~A.~Abramov, M.~van~Hoeij (1997): A method for the Integration of Solutions of Ore Equations, {\em Proc.\ ISSAC'97}, 172 -- 175. \bibitem{APP} S.~A.~Abramov, P.~Paule, M.~Petkov\v sek (1998): $q$-Hy\-per\-geo\-met\-ric solutions of $q$-difference equations, {\em Discrete Math.} {\bf 180}, 3--22. \bibitem{AZ} S.~A.~Abramov, E.~V.~Zima (1997): Minimal completely factorable annihilators, {\em Proc.\ ISSAC'97}, 290 -- 297. \bibitem{BP} M.~Bronstein, M.~Petkov\v sek (1995): An introduction to pseudo-linear algebra, {\em Theoretical Computer Science\/} {\bf 157}, 3 -- 33. \bibitem{Ch} F.~Chyzak (1997): An extension of Zeilberger's fast algorithm to general holonomic functions, {\em Proc.\ FPSAC'97\/}, 172--183. %F.~Chyzak (1996): %$\partial$-finite functions, %{\em INRIA. Algorithm seminar 1995--1996\/}, 43--46. \bibitem{ChS} F.~Chyzak, B.~Salvy (1996): Non-commutative elimination in Ore algebra proves multivariate holonomic identities, {\em INRIA Research Report\/}, No 2799. \bibitem{Cohn} P. M. Cohn (1995): Skew Fields, Theory of General Division Rings, Encyclopedia of Mathematics and its Applications, {\em Cambridge University Press}, {\bf 57}. \bibitem{Gos} R.~W.~Gosper, Jr. (1978): Decision procedure for indefinite hypergeometric summation, {\em Proc.\ Natl.\ Acad.\ Sci.\ USA} {\bf 75}, 40 -- 42. \bibitem{issac96} M. van Hoeij (1996): Rational Solutions of the Mixed Differential Equation and its Application to Factorization of Differential Operators, {\em Proc. ISSAC'96}, 219--225. \bibitem{O} O.~Ore (1933): The theory of non-commutative polynomials, {\em Ann. Maths.\/} {\bf 34}, 480 -- 508. \end{thebibliography} \end{document}