Computer Algebra for
Concrete Mathematics

Part 1: Introductory Examples

Part 2: Examples from HW and Lecture

Peter.Paule@risc.jku.at

May 27, 2014, JKU

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

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

f[x_]:=1

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}]

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

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]

Let' s check :

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

Next we guess a recurrence :

GuessRE[upto11,a[n]]

GuessedRec = %[[1]]

?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

Homework 19/21

Suppose  f(x)=(∑_(n=0)^∞)f(n)(x^n) satisfies the DE

f'(x)=-f(x)+((f(x))/(1-x));

find a recurrence for (Subscript[(f(n)), n≥ 0]).

DE2RE[{f'[x]==-f[x]+((f[x])/(1-x))},f[x],a[n]]

NOTE.  This is the recurrence we had in HW18. (There: a[0]=1,a[1]=0.)

Homework 20/22

Given the rec from HW18:

HW18={a[n]+(1+n) a[1+n]+(-2-n) a[2+n]==0,a[0]==1,a[1]==0};

find a DE eq for A(x)=(∑_(n=0)^∞)a(n)(x^n).

RE2DE[HW18, a[n], A[x]]

DSolve[{A'[x]==(x/(1-x
))A[x],A[0]==1},A[x],x]

Binary Trees

t[0]=1;t[n_]:=(∑_(k=0)^(n-1))t[k] t[n-1-k];

Table[t[n],{n,0,5}]

re=GuessRE[%,a[n]]

RSolve[{a[n+1]==((2(2n+1))/(n+2))a[n],a[0]==1}, a[n],n]

RE2DE[re[[1]],a[n],f[x]]

DSolve[{-1-(-1+2 x) f[x]-(-x+4 (x^2)) f'[x]==0,f[0]==1},f[x],x]

Series[((1-(Sqrt[1-4 x]))/(2 x)),{x,0,6}]

Table[(1/(n+1))(SubStar[(({{2n}, {n}}))]),{n,0,6}]

Unprotect[Show];Gosper[(1/(k+1))(SubStar[(({{2k}, {k}}))])(1/(n-k))(SubStar[(({{2(n-k)-1}, {n-k-1}}))]),{k,0,n-1}]

Prove[]

Plot[Gamma[z],{z,-3,3}]

?Gamma

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?

RE2DE[re,fib[k],F[x]]

RE2L[re,fib[k],6]

Symbolic Summation

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[]