Computer Algebra for
Concrete Mathematics

Part 3: HWs 38 to 41

Peter.Paule@risc.jku.at

June 17, 2014, JKU

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

InputForms: Binomials

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

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

Homework 38

f[x_]:=((1+2x)/(1-2x))

Series[f[x],{x,0,10}]

CoefficientList[%,x]

rec38=GuessRE[%,a[n]][[1]]

RSolve[rec38,a[n],n]

NOTE. The value a[1] does not fit into the recursive pattern!

RSolve[-2 a[1+n]+a[2+n]==0,a[n],n]

Observation: a[0]=(2^(-1)) C[1],a[1]= C[1] , and therefore

RSolve[{-2 a[1+n]+a[2+n]==0,a[0]==2,a[1]==4},a[n],n]

Consequently, let' s do a variation of the problem starting at n = 1 :  Setting b[n]:=a[n+1] for n≥0 we obtain,

RSolve[{-2 b[n]+b[1+n]==0,b[0]==4}, b[n],n]

Summarizing, we found that

a[0]=1 and for n≥1: a[n]=b[n-1]=(2^(2+n))

Alternative Solution

Recall : we found the following recursive description of the Taylor coefficients :

rec38

Clear[f]

de38=RE2DE[rec38,a[n], f[x]]

DSolve[de38, f[x],x]

NOTE. In fact, we need not solve a proper differential equation!

Homework 39

f[x_]:=(((((1+x)/(1-x))))^2)

Series[f[x],{x,0,10}]

CoefficientList[%,x]

rec39=GuessRE[%,a[n]][[1]]

RSolve[rec39,a[n],n]

NOTE. The value a[1] does not fit into the recursive pattern!

RSolve[-n a[n]+(-2+n) a[1+n]+a[2+n]==0,a[n],n]

Observation: If C[2]=0 then a[n]->n C[1]and therefore 
a[0]=0 *C[1],a[1]=1* C[1] ,a[2]=2*C[1]; consequently:

RSolve[{-n a[n]+(-2+n) a[1+n]+a[2+n]==0,a[0]==0,a[1]==4,a[2]==8},a[n],n]

Consequently, let' s do a variation of the problem starting at n = 1 :  Setting b[n]:=a[n+1] for n≥0 we obtain,

RSolve[{{-(n+1) b[n]+(-2+(n+1)) b[1+n]+b[2+n]==0,b[0]==4,b[1]==8}}, b[n],n]

Summarizing, we found that

a[0]=1 and for n≥1: a[n]=b[n-1]=4n

Alternative Solution

Recall : we found the following recursive description of the Taylor coefficients :

rec39

Clear[f]

de39=RE2DE[rec39,a[n], f[x]]

DSolve[de39, f[x],x]

NOTE. In fact, NOW we needed to solve a proper differential equation!

Homework 40

f[x_]:=(Sqrt[((1+x)/(1-x))])

Series[f[x],{x,0,20}]

FactorInteger[{231,429,6435}]

Series[f[x],{x,0,10}]

CoefficientList[%,x]

rec40=GuessRE[%,a[n]][[1]]

RSolve[rec40,a[n],n]

Alternative Solution 1

Recall : we found the following recursive description for the Taylor coefficients :

rec40

Clear[f]

de40=RE2DE[rec40,a[n], f[x]]

DSolve[de40, f[x],x]

NOTE. In fact, again we need to solve a proper differential equation!

Alternative Solution 2

Recall : we found the following sum description for the Taylor coefficients :

(∑_(k=0)^n)(SubStar[(({{-1/2}, {k}}))])(SubStar[(({{1/2}, {n-k}}))])(((-1))^k)

(∑_(k=0)^(2n))(SubStar[(({{-1/2}, {k}}))])(SubStar[(({{1/2}, {2n-k}}))])(((-1))^k)

%-((Pochhammer[(1/2),n])/( n!))//FullSimplify

CHECK for the odd values a[2n+1], n≥0:

(∑_(k=0)^(2n+1))(SubStar[(({{-1/2}, {k}}))])(SubStar[(({{1/2}, {2n+1-k}}))])(((-1))^k)

QUESTION : Do you trust Mathematica? ⟶ See the example with Mathematica 5.2!

Let' s use the RISC package to do the summation :

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

We have seen this recurrence already :

rec40

Let' s look at the subsequence a[2 n], n >= 0 :

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

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

RSolve[{2 n (1+2 n)b[n]+(-9-16 n-8 (n^2))b[n+1]+2 (2+n) (3+2 n)b[n+2]==0,b[0]==1,b[1]==1/2}, b[n],n]

(((-(1/2)+n)!)/((Sqrt[π]) n!))-((Pochhammer[(1/2),n])/( n!))//FullSimplify

EXPLANATION : The recurrence factors! The recurrence in operator notation :

(2 (2+n) (3+2 n)(Subscript[S, n]^2)+(-9-16 n-8 (n^2))(Subscript[S, n])+2 n (1+2 n)I)b[n]==0,

and we have

2 (2+n) (3+2 n)(Subscript[S, n]^2)+(-9-16 n-8 (n^2))(Subscript[S, n])+2 n (1+2 n)I
              = ((2n+3)(Subscript[S, n])-2n I)(2(n+1)(Subscript[S, n])-(2n +1)I)

Factor[-(2n+3)^2-2n 2(n+1)]

Compare the red operator to the recurrence for b[n] = a[2 n] :

rec40even

Homework 41

f[x_]:=Log[((1+x)/(1-x))]

Series[f[x],{x,0,20}]

CoefficientList[%,x]

rec41=GuessRE[%,a[n]][[1]]

RSolve[rec41,a[n],n]

Let' s look at the general solution :

RSolve[-n a[n]+(2+n) a[2+n]==0,a[n],n]

Solve[{2==((2 C[1])/1)+((2 (((-1))^1) C[2])/1),0==((2 C[1])/2)+((2 (((-1))^2) C[2])/2)},{C[1],C[2]}]

Consequently, a[0] = 0, and for n≥1,

a[n]=(1/n)-(( (((-1))^n) )/n);

this means, for n≥0,

a[2n]=0  and a[2n+1]= (2/(2n+1)).

NOTE. Alternatively, we could have looked at the subsequence b[n]=a[2n+1], n≥0:

rec41odd=GuessRE[{2,(2/3),(2/5),(2/7),(2/9),(2/11),(2/13)},b[n]][[1]]

RSolve[rec41odd,b[n],n]

Alternative Solution

Recall : we found the following recursive description for the Taylor coefficients :

rec41

Clear[f]

de41=RE2DE[rec41,a[n], f[x]]

DSolve[de41, f[x],x]

NOTE. Here we need to solve just an integration problem! (And not a proper differential equation!)

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

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

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

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

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