Computer Algebra for
Concrete Mathematics

Part 1: Introductory Examples

Peter.Paule@risc.jku.at

April 8, 2014, JKU

Preamble

This is the first of several Mathematica notebooks supplementing the Lecture (VL)
“Computer Algebra for Concrete Mathematics” - and also the respective UE.

Homework Problems (for those attending the UE)

NOTE. In the UE on Tuesday, April 29, we will go throught this notebook and discuss its content and the related CA-Homeworks.

CA Homework 1

Install the required RISC packages (see below) on your computer. To this end, go to

www.risc.jku.at/research/combinat/
software/source/mathematica/ergosum

and see the instructions there.  To pick up the packages at the RISC site, you need the following access information:

user ID: comb      
password: HaveFun

CA Homework 2

Consider Mathematica’s output to “RSolve”

re={-fib[k]-fib[1+k]+fib[2+k]==0,fib[0]==1,fib[1]==1};

RSolve[re,fib[k],k]

Question : Is this a correct solution to the recurrence?

Some Symbolic Packages

The following packages of my RISC Combinatorics Group are used:

NOTE. First you have to pick them up at the web page given above...

<<RISC`fastZeil`

Fast Zeilberger Package version 3.60
written by Peter Paule, Markus Schorn, and Axel Riese
Copyright 1995-2009, Research Institute for Symbolic Computation (RISC),
Johannes Kepler University, Linz, Austria

<<RISC`GeneratingFunctions`

Package GeneratingFunctions version 0.7 written by Christian Mallinger
Copyright 1996-2009, Research Institute for Symbolic Computation (RISC),
Johannes Kepler University, Linz, Austria

Software

Packages of the RISC Combinatorics Group

Freely available at: http://www.risc.jku.at/research/combinat/software

More than 3,000 users world-wide. (In average two password requests per week.)

Audience: (pure and applied) mathematicians, but also many physicists; also  engineers,  etc.

InputForms: Binomials

(SubStar[(({{n_}, {k_}}))]):=Binomial[n,k]

(SubStar[(({{a}, {3}}))])

Automatic Guessing

I.Q. Tests
Setzen Sie die Reihe fort: 1  1  2  3  5  8  13  21  ?
Es gibt zwei Lösungsmoeglichkeiten, eine leichte und eine schwierigere. Versuchen Sie, ob Sie beide finden koennen.
[Aufgabe 13, Denksport I für Superintelligente; ``Check Your Own I.Q.’’, Hans J. Eysenck, 1966]

Computer  Solution
with the RISC combinatorics package GeneratingFunctions
[Christian Mallinger, ``Algorithmic Manipulations and Transformations of Univariate Holonomic Functions and Sequences’’, Diplomarbeit, RISC-Linz, 1996]

GuessNext2Values[Li_]:=Module[{rec},rec=GuessRE[Li,c[k],{1,2},{0,3}];
RE2L[rec[[1]],c[k],Length[Li]+1]]

GuessNext2Values[{1,2,4,8,16}]

GuessNext2Values[{1,3,6,10,15,21}]

GuessNext2Values[{1,1,2,6,24,120}]

GuessNext2Values[{1,1,2,3,5,8,13,21}]

Book Solution

“34. (Leicht. Jede Zahl wird durch Subtraktion der folgenden von der naechstfolgenden Zahl gebildet: 2-1 = 1 usw. bis 34-21 = 13, also ist die fehlende Zahl 34.

Schwierig. Das Quadrat jeder Zahl unterscheidet sich um 1 vom Produkt der Zahlen rechts und links von ihr: (1^2)=1, 2×1=2; (2^2)=4, 1×3=3; usw. bis (21^2)=441, 13×34=442.)"

{1,1,2,3,5,8,13,21,34}

Book Solution

“34. (Leicht. Jede Zahl wird durch Subtraktion der folgenden von der naechstfolgenden Zahl gebildet: 2-1 = 1 usw. bis 34-21 = 13, also ist die fehlende Zahl 34.

Schwierig. Das Quadrat jeder Zahl unterscheidet sich um 1 vom Produkt der Zahlen rechts und links von ihr: (1^2)=1, 2×1=2; (2^2)=4, 1×3=3; usw. bis (21^2)=441, 13×34=442.)"

{1,1,2,3,5,8,13,21,34}

Note. Die “schwierige” Lösung entspricht der Cassini (1680) Identität.

F[n+1]F[n-1]-((F[n])^2) = (((-1))^(n+1)),         n⩾1.

We shall see, this can be proved automatically with the GeneratingFunctions package!

Idea behind Automatic Guessing

?GuessRE

GuessRE[{1,2,4,8,16},c[k]]

GuessRE[{1,3,6,10,15,21},c[k]]

GuessRE[{1,1,2,6,24,120},c[k]]

GuessRE[{1,1,2,3,5,8},F[k]]

Application: QuickSort

Recurrences : guessing, etc.

We start with the recursive description:

{F[0]=0,F[1]=0}

F[n_]:=(1/n)( (n-1)n+2 (∑_(k=0)^(n-1))F[k])

upto11=Table[F[n],{n,0,11}]

Let’s guess the next two values:

GuessNext2Values[upto11]

Recall: we guessed the next two values:

GuessNext2Values[upto11]

Let' s check :

upto13=Table[F[n],{n,0,13}]

Next we guess a recurrence :

GuessRE[upto11,a[n]]

GuessedRec = %[[1]]

We guessed the following recurrence for the QuickSort numbers:

GuessedRec

?RE2L

RE2L[GuessedRec,a[n],13]

Let' s check :

upto13=Table[F[n],{n,0,13}]

Another recurrence for the QuickSort numbers:

rec={(n+3) a[n+3]-(3n+8) a[n+2] +(3n+7)a[n+1]-(n+2)a[n]==0,a[0]==0,a[1]==0,a[2]==1};

RE2L[rec,a[n],13]

Let' s check :

upto13=Table[F[n],{n,0,13}]

This confirms that this is indeed another recursive description of the QuickSort numbers!

Differential Equations from Recurrences

So far we have not proved that our guessed recurrence

GuessedRec

is indeed a valid recurrence for the QuickSort numbers.

We will prove this by transforming the GuessedRec into a DIFFERENTIAL EQUATION  for the generating function

f(x)=(∑_(n=0)^∞)F(n)(x^n)=(∑_(n=0)^∞)a[n](x^n)= -((2x)/(((1-x))^2))-(2/(((1-x))^2))log(1-x)

GuessedDE =RE2DE[GuessedRec,a[n],f[x]]

Recall: we guessed the DE

GuessedDE

We let Mathematica solve it :

DSolve[GuessedDE,f[x],x]

Let' s try the same with our second recursive description :

rec

Let' s try the same with our second recursive description :

recDE=RE2DE[rec,a[n],f[x]]

NOTE. This is the same differential equation as derived in the lecture!

DSolve[recDE,f[x],x]

FullSimplify[((2 I (π+I x+I Log[-1+x]))/(((-1+x))^2))-(-((2x)/(((1-x))^2))-(2/(((1-x))^2))Log[1-x])]

((2 (I π+Log[1-x]-Log[-1+x]))/(((-1+x))^2)) /.x->-0.7

Consider the sum

(∑_(k=0)^(n-2))k k!

For which values of n is this answer correct?

Alternatively, we can use the procedure from the RISC package `fastZeil`:

Unprotect[Show];Gosper[k k!,{k,0,n-2}]

Note that -in contrast to Mathematica-  the output of `Gosper` includes 
additional information about the domain of admissible n!

Execute

Prove[]

Explain why this is delivering a proof of the `Gosper output'.

An Automatic Proof of the Binomial Theorem

We prove the  binomial theorem in the form

(∑_(k=0)^n)(({{n}, {k}})) (x^k)(y^(n-k))=(((x+y))^n)

Set

g[n_] := (∑_(k=0)^n)(SubStar[(({{n}, {k}}))]) (x^k)(y^(n-k))

{g[0],g[1],g[2],g[3],g[4],g[5],g[6],g[7],g[8]} //Factor

Proof.

Unprotect[Show];Zb[(SubStar[(({{n}, {k}}))])(x^k)(y^(n-k)),{k,0,n},n,1]

Prove[]