Hagenberg Research
                                   Name of Author∗
                                 September 27, 2012
                                        Abstract
            This is just an exercise.
1      Computer-Assisted Discovery and Proving
First we comment on computer-assisted guessing in the context of mathe-
matical discovery. Then we turn to the activity of proving, more precisely,
to proving methods where computer algebra algorithms are used. Here we
restrict to this special type of computed-assisted proving; for general mathe-
matical proving machines like the THEOREMA system developed at RISC.
1.1      I.Q. Tests, Rabbits, and the Golden Section
Let us consider the following problem taken from an I.Q. test [2, Aufgabe 13,
Denksport I fuer Superintelligente] from the sixties of the last century:
                     Continue the sequence 1, 1, 2, 3, 5, 8, 13, 21.
     In the 21st century we let the computer do the problem. To this end we
load the RISC package GeneratingFunctions written by C. Mallinger [4] in
the computer algebra system Mathematica:
In[1]:=    GeneratingFunctions.m
In the next step we input a little program that can be used to solve such I.Q.
tests automatically:
   ∗
     This is an exercise for the RISC course “Computer based working environments”.
                                             
In[2]:= GuessNext2Values[Li ] := Module[{rec},
          rec = GuessRE[Li,c[k],{1,2},{0,3}];
          RE2L[rec[[1]],c[k],Length[Li]+1]]
Finally the problem is solved automatically with
In[3]:= GuessNext2Values[{1, 1, 2, 3, 5, 8, 13, 21}]
Out[3]= {1, 1, 2, 3, 5, 8, 13, 21, 34, 55}
To produce additional values is no problem:
In[4]:= GuessNext2Values[{1, 1, 2, 3, 5, 8, 13, 21, 34, 55}]
Out[4]= {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144}
    What is the mathematical basis for such automatic guessing? The answer
originates in a simple observation: Many of the sequences (xn )n≥0 arising in
practical applications (and in I.Q. tests!) are produced from a very simple
pattern; namely, linear recurrences of the form
          pd (n)xn+d + pd−1 (n)xn+d−1 + · · · + p0 (n)xn = 0,              n ≥ 0,
with coefficients pi (n) being polynomials in n. So packages like Mallinger’s
GeneratingFunctions try to compute-via an ansatz using undetermined
coefficients-a recurrence of exactly this type. For the I.Q. example above
a recurrence is obtained by
In[5]:= GuessRE[{1, 1, 2, 3, 5, 8, 13, 21},f[n]]
Out[5]= {{−f [n] − f [1 + n] + f [2 + n] == 0, f [0] == 1, f [1] == 1}, ogf}
Since only finitely many values are given as input, the output recurrence
fn+2 = fn+1 + fn (n ≥ 0) can be only a guess about a possible building
principle of an infinite sequence. However, such kind of automated guessing
is becoming more and more relevant to concrete applications. For instance,
an application from mathematical chemistry can be found in [1] where a
prediction for the total number of benzenoid hydrocarbons was made. Three
years later this predication was confirmed [5]. Recently, quite sophisticated
applications arose in connection with the enumeration of lattice paths and
also with quantum field theory.
    In 1202 Leonard Fibonacci introduced the numbers fn . The fact that
f0 = f1 = 1, and
              fn+2 = fn+1 + fn ,  n ≥ 0,                  (1)
                                                 
    in Fibonacci’s book was given the following interpretation: If baby rabbits
become adults after one month, and if each pair of adult rabbits produces
one pair of baby rabbits every month, how many pairs of rabbits, starting
with one pair, are present after n months?
    A non-recursive representation of (1) is the celebrated Euler-Binet for-
mula
		...
The number (1 + 5)/2 ≈ 1.611803, the golden ratio, is important in many
parts of mathematics as well as in the art world. For instance, Phidias is
said to have used it consciously in his sculpture.
    Mathematicians gradually began to discover more and more interesting
things about Fibonacci numbers fn ; see e.g. [3]. For example, a typical
sunflower has a large head that contains spirals of tightly packed florets,
usually with f8 = 34 winding in one direction and f9 = 55 in another.
    Another observation is this: Define gn as a sum over binomial coefficients
of the form                         
		...
From the values g0 = 1, g1 = 1, g2 = 2, g3 = 3, g4 = 5, and g5 = 8 it
is straight-forward to conjecture that the sequence (gn )n≥0 is nothing but
the Fibonacci sequence (fn )n≥0 . In the next subsection we shall see that
nowadays such statements can be proved automatically with the computer.
References
[1] F. Chyzak, I. Gutman, and P. Paule. Predicting the Number of Hexagonal
    Systems with 24 and 25 Hexagons. MATCH, 40:139–151, 1999.
[2] Hans J. Eysenck. Check Your Own I.Q. Rowohlt, 1966.
[3] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics.
    Addison-Wesley, 2nd edition edition, 1994.
[4] Christian Mallinger. Algorithmic Manipulations and Transformations of
    Univariate Holonomic Functions and Sequences. Master’s thesis, RISC-
    Linz, August 1996.
[5] Markus Voege, Anthony J. Guttmann, and Iwan Jensen. On the Num-
    ber of Benzenoid Hydrocarbons. Journal of Chemical Information and
    Computer Sciences, 42(3):456–466, 2002.