axiom-developer
[Top][All Lists]

[Axiom-developer] [Guessing formulas for sequences]

 From: anonyme Subject: [Axiom-developer] [Guessing formulas for sequences] Date: Sun, 20 Mar 2005 03:38:10 -0600

Changes
http://page.axiom-developer.org/zope/mathaction/GuessingFormulasForSequences/diff
--

??changed:
-  We present a software package that guesses formulas for sequences of rational
-  numbers, rational functions and also more complicated formulas, given the
-  first few terms. Thereby we extend and complement Christian Krattenthaler's
-  program 'Rate', Doron Zeilberger's program 'GuessRat' and the relevant parts
-  of Bruno Salvy and Paul Zimmermann's 'GFUN'.
-
-  Introduction
-
-    For some a brain-teaser, for others one step in proving their next theorem:
We present a software package that guesses formulas for sequences of rational
numbers, rational functions and also more complicated formulas, given the first
few terms. Thereby we extend and complement Christian Krattenthaler's program
\Rate, Doron Zeilberger's program 'GuessRat' and the relevant parts of Bruno
Salvy and Paul Zimmermann's 'GFUN'.

Introduction

For some a brain-teaser, for others one step in proving their next theorem:

??changed:
-$$-\begin{split} \begin{eqnarray} ??changed: -\end{split} -$$
\end{eqnarray}

??changed:
-
-    A formula for Sequence (1), is almost trivial to guess: it seems
-obvious that it is $n^2$. More generally, if we believe that the sequence in
-question is generated by a polynomial, we can simply apply interpolation.
-However, how can we "know" that a polynomial formula is appropriate? The answer
-is quite simple: we use all but the last term of the sequence to derive the
-formula. After this, the last term is compared with the value predicted by the

A formula for Sequence (1), is almost trivial to guess: it seems obvious
that
it is $n^2$. More generally, if we believe that the sequence in question is
generated by a polynomial, we can simply apply interpolation.  However, how
can we "know" that a polynomial formula is appropriate? The answer is quite
simple: we use all but the last term of the sequence to derive the formula.
After this, the last term is compared with the value predicted by the

??changed:
-paralleling interpolation, Pad\'e approximation may be used to find out whether
paralleling interpolation, Pade approximation may be used to find out whether

--removed:
-

??changed:
-able to guess a formula using interpolation, Pad\'e approximation or one of its
able to guess a formula using interpolation, Pade approximation or one of its

??changed:
-with the 'Axiom' package 'Guess'.
-
-The package provides currently four primitive guessing functions, namely:
with the 'Axiom' package 'Guess'. The package provides currently four primitive
guessing functions, namely:

??changed:
-    term as in (5),
term as in (5),

??changed:
-    constant coefficients, and
constant coefficients, and

??changed:
-    polynomial coefficients.
polynomial coefficients.

--removed:
-

??changed:
-have to use the package 'GuessPolynomial' instead of
-'GuessInteger'::
have to use the package 'GuessPolynomial' instead of 'GuessInteger'.
For example::

??changed:
-the methods described above. For example, they fail for
-Sequences (3) and \eqref{eq4}. However, the functions
-demonstrated above all had an argument 'n+->n' we did not explain yet!
the methods described above. For example, they fail for Sequences (3) and (4).
However, the functions demonstrated above all had an argument 'n+->n' we did
not explain yet!

Some remarks

- All of the presented guessing algorithms are insensitive to the shift
operator. I.e., if a formula for the sequence $(s_1,s_2,\dots,s_m)$ can
be
guessed, then the corresponding formula for $(s_2,s_3,\dots,s_{m+1})$
will
be found, too.

- Except of the class of functions covered by 'guessExpRat', all are
closed under addition. I.e., if formulas for $(s_1,s_2,\dots,s_m)$ and
$(t_1,t_2,\dots,t_m)$ can be guessed, then also for
$(s_1+t_1,s_2+t_2,\dots,s_m+t_m)$. However, the class of functions of
type (5) is not even closed under addition of a constant! On the other
hand, all classes are closed under multiplication.

- Note that the class of functions covered by 'guessPRec', i.e., the
class of $D$-finite functions, is closed under the operator $\Delta_n$.
Thus, it does not make to try to guess a function for some sequence $s$
with::

guess(n, s, n+->n, [guessPRec], [guessSum]).

The situation is very different, if the operator 'guessProduct' is
specified, too. The class of functions covered by::

guess(n, s, n+->n, [guessPRec], [guessSum, guessProduct])

is bigger than the class of functions::

guess(n, s, n+->n, [guessPRec], [guessProduct])!

--