Computer Algebra

for Concrete Mathematics

Summer semester 2024

[Link]@[Link]

In this lecture basic skills and techniques will be elaborated which are rel-
evant to simplify formulas related to enumeration. Special emphasis is put
on tools that support the student for the analysis of algorithms (best case,
worst case and average case). In particular, the participant gets acquainted
to apply these computer algebra tools to non-trivial examples.
The content of the lecture can be summarized by the following key words:

• algorithmic treatment of formal power series;

• c-finite and holonomic functions/sequences;

• recurrence solving;

• basic aspects of asymptotics;

• symbolic summation.

A major emphasis of the lecture is to present the basic notions, to develop

the basic ideas of the underlying algorithms and to put computer algebra
into action for concrete examples.
In addition, many of the topics discussed in the lecture can be found in the
books

• Concrete Mathematics - A Foundation for Computer Science by

[Link], [Link] and [Link] (Addison-Wesley, 1994),

• The Concrete Tetrahedron by Manuel Kauers and Peter Paule

(Springer Wien, 2011).

1
Contents
1 Introduction 3
1.1 A case study for SelectionSort and summation . . . . . . . . . . . . . . . . . . . 3
1.2 Some basic notions for asymptotics . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 A case study for QuickSort and recurrences . . . . . . . . . . . . . . . . . . . . . 9
1.4 A case study for Binary Search Trees (BST) . . . . . . . . . . . . . . . . . . . . 14

∗
2 Recall: basic notions from algebra 18

3 Generating functions and formal power series 21

3.1 Differentiation and division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 Finding closed forms for generating functions . . . . . . . . . . . . . . . . . . . . 30

4 Application: binary trees 33

5 Formal power series: Part 2 42

5.1 Connection to analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.2 Quotients of formal power series . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.3 Convergence in K[[x]] and K((x)) . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.4 Composition in K[[x]] (resp. K((x))) . . . . . . . . . . . . . . . . . . . . . . . . 53

6 c-finite sequences 57
6.1 Solving c-finite recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.2 Application: AVL-trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.3 Closure properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

7 Holonomic sequences and power series 72

2
Lecture from March 05, 2024

1 Introduction
In this lecture we will deal in strong interaction with generating functions, recurrences, asymp-
totics and summation. This interplay can be visualized also as follows:

generating o /
summation
: O
functions
O d

 z $ 
recurrences o /
asymptotics

In the introduction we will illustrate the interaction of recurrences, summation and asymptotics.
The machinery of generating functions (formal power series) will be introduced in Section 3
below.

1.1 A case study for SelectionSort and summation

We start with an example of the well-known sorting algorithm SelectionSort.

Example 1.1. We apply SelectionSort to (5, 3, 8, 2). This means that we find a smallest
element from the list/array and move it to the beginning. Afterwards we proceed with the
list/array where the first entry is ignored. In this way we get the following operation steps:

5 8 3 2

2 8 3 5

2 3 8 5

2 3 5 8

Remark: if one deals with an array, one can move the smallest element to the right place by
swapping elements accordingly.
In the following (for SelectionSort and later for QuickSort) we will estimate the time complexity
by counting the number of comparisons. In this regard, the following consideration is immedi-
ate: In order to find the smallest element 2 in (5, 8, 3, 2) one needs 3 comparisons; to find the

3
smallest element 3 in (8, 3, 5), one needs 2 comparisons; and to find the smallest element 5 in
(8, 5), one needs 1 comparison. In total

3+2+1=6

comparisons are needed. In general, if

F (n) = number of pairwise comparisons to selection-sort n elements (n ≥ 0)

we get

F (n) = (n − 1) + (n − 2) + · · · + 2 + 1
Xn
= (n − k)
k=1
n−1
k→n−k
X
= k
k=1
why? n(n − 1)
= .
2
Notation 1.2. We will use the following conventions:

N := {0, 1, 2, 3, . . . }
N∗ := {1, 2, 3, . . . }
b
X
f (k) := 0 if a > b
k=a
Yb
f (k) := 1 if a > b.
k=a

One way to simplify the Gauss sum nk=1 k (or to show that it equals to n(n−1)
P
2
) is to sum it
twice (in the usual and in the reversed order):

1 + 2 + 3 + ... + n
+ n + (n − 1) + (n − 2) + . . . + 1
= (n + 1) + (n + 1) + (n + 1) + . . . + (n + 1) = n(n + 1).

This gives
n
X n(n + 1
k = 1 + 2 + ··· + n = .
k=1
2
Alternatively, one can consider the picture (the black balls represent the sum)

4
 1 + 2 + 3 + 4 + 5 ... +n  =n(n+1)
• • • • • ... • 

⊛ • • • • ... •




⊛ ⊛ • • • ... •



.. n+1
⊛ ⊛ ⊛ • • ... . 
• •

⊛ ⊛ ⊛ ⊛ ... 


•

⊛ ⊛ ⊛ ⊛ ⊛ ... 


⊛ ⊛ ⊛ ⊛ ⊛ ... ⊛
| {z }
n
in order to extract the identity.
HW 1. Try to apply the Gauß-method to sum
Pn
(a) k=0 (2k + 1)
Pn 2
(b) k=1 k
Pn 3
(c) k=1 k

Find and prove a formula for (a), (b) and (c).

Note that the above proof can be also reflected with the following sum manipulations:

n−1 n−1 n−1 n−1

k→n−k
X X X X
k = (n − k) = n− k
k=1 k=1 k=1 k=1
n−1
X n−1
X
= n 1− k
k=1 k=1
| {z }
n−1

⇓
n−1
X
2 = n(n − 1).
k=1

Throughout this lecture the harmonic numbers will play a central role.
Definition 1.3. For n ∈ N, we define
n
X 1
Hn = ;
k=1
k

note that with our convention from above we have H0 = 0.

HW 2. Prove for all n ∈ N that
n−1
X k 2n
= Hn − .
k=0
(k + 1)(k + 2) n+1

5
HW 3. Let f : Z → C and a, b ∈ Z with a ≤ b.

1. For
b
X
S(a, b) := (f (k + 1) − f (k))
k=a

show that
S(a, b) = f (b + 1) − f (a).

2. Suppose in addition that f (k) ̸= 0 for all k with a ≤ k ≤ b. For

b
Y f (k + 1)
P (a, b) :=
k=a
f (k)

show that
f (b + 1)
P (a, b) = .
f (a)
HW 4. Use the previous homework to find a closed form for
n  
Y 1
an := 1− 2 .
k=2
k

BP 1. Consider the function exp : R → R defined by

∞
X xn
x 7→ .
n=0
n!

p(x)
Prove: there is no rational function r(x) ∈ R(x) (i.e., r(x) = q(x)
for polynomials p, q ∈ R[x])
such that
exp(x) = r(x) ∀x ∈ U
where U ⊆ R is some non-empty open interval.

HW 5. Given a tower of n discs, initially stacked in decreasing size on one of three pegs.
Transfer the entire tower to one of the other pegs, moving only one disc at each step and never
moving a larger one onto a smaller one. Find an , the minimal number of moves (n ≥ 0).

HW 6. How many slices of pizza can a person maximally obtain by making n straight cuts
with a pizza knife. Let Pn (n ≥ 0) be that number.

BP 2. Prove that there is no rational function r(x) ∈ C(x) such that

Hn = r(n)

for all n ∈ N with n ≥ λ for some λ ∈ N.

6
Example 1.4. What is the maximal possible overhang of n cards (beer coaster)?
Let us suppose that a card has length 2. Then with 1 card we get the overhang 1:

1 1
.

table

If we are given two cards, we start with

1 1
.
.

table

and observe that we cannot move the top card further. Thus we move the card below further
and further away, and it is not difficult to see that the balance point is reached with the
overhang 1 + 21 = 23 . Thus we get the following picture:
1
2
+1
.
. .

table

If we are given three cards, the balance point will be at position 1 + 12 + 13 = 11

6
.
With 4 cards the overhang will be H4 = 1 + 21 + 13 + 14 = 12
25
, which is more than one card length.
With 52 cards, we get the overhang H52 = 2.27 · 2, i.e., it is twice the card length. In general,
the maximal overhang of n cards is Hn .
What happens if we stack more and more cards. Can we make the overhang arbitrarily large?
Questions like this lead immediately to asymptotic considerations.

1.2 Some basic notions for asymptotics

We start with the big-O notation.
Definition 1.5. For1 g : N → R we define
O(g) = {f : N → R | ∃cf ∈ R, n0 ∈ N ∀n ≥ n0 : |f (n)| ≤ cf |g(n)|}.
Example 1.6. We have
222 1
222
2n ∈ O(n), 2n − 5 ∈ O(n), 2 · n ∈ O(n), · n ∈ O(n).
2 222
22 2
1
Note that the function g can be also interpreted as a the sequence (g(n))n≥0 with entries from R.

7
Lecture from March 12, 2024
The following theorem states that the harmonic numbers and the log-function grow similarly
fast.
Theorem 1.7. We have
Hn − log(n) − γ ∈ O( n1 );
here log(n) := ln(n) denotes the natural logarithm (to the basis e) and γ = 0, 5772156 · · · ∈ R
is Euler’s constant2

Proof. For a proof see the book Concrete Mathematics by Graham/Knuth/Patashnik.

Example 1.8. Going back to Example 1.4 we conclude with

lim log(n) = ∞
n→∞

that the overhang can be (theoretically) arbitrary long if sufficiently many cards are available.
However, the overhang grows dramatically low. E.g., suppose that the card length is 10cm (i.e.,
one unit corresponds to 5cm). Then we can produce an overhang of more than 100m with n
cards, if
2000 ≤ Hn ≤ log(n) + 1
holds. Thus n ≥ e1999 , i.e., we must take around 1.429 · 10868 cards; however, one estimates
that there are only around 1080 atoms in the universe...

In particular, we can conclude with this theorem that there is a constant c ∈ R and n0 ∈ N
(actually one can choose n0 = 1) such that
c
| Hn − log(n) − γ | ≤
| {z } n
:=an ∈R

holds for all n ≥ n0 = 1. This implies that (an )n≥0 converges (in the analysis sense) to 0, i.e.,

lim an = 0
n→∞

⇕
lim (Hn − log(n) − γ) = 0
n→∞

⇕
lim (Hn − log(n)) = γ.
n→∞

Definition 1.9. For a, b : N → R we define

a(n)
a(n) ∼ b(n) ⇔ lim = 1.
n→∞ b(n)

In this case, we also say that a(n) and b(n) are asymptotically equal.
2
So far it is not known, if γ ∈ Q or if γ is irrational.

8
We remark that ∼ is an equivalence relations.
HW 7. Show that Hn ∼ log(n).

Another important fact is Stirling’s formula that can be stated as follows; the proof can be
found again in Concrete Mathematics.
Theorem 1.10.  n n √
n! ∼ 2πn.
e
Note: Since nn = (elog(n) )n = en log(n) , we get
√
n! ∼ en(log(n)−1) 2πn.

1.3 A case study for QuickSort and recurrences

We turn to QuickSort and sort the array

44 13 9 29 71 67 5 8 15

with n = 9 elements. In each step we split the array by choosing a pivot element at random.
Here we take, e.g., 29. We swap it to the right side and focus on the remaining array:

44 13 9 15 71 67 5 8 29.

Next, we split the array: all elements which are smaller than 29 are moved to the left-hand
side, and all elements which are larger than 29 are moved to the right-hand side. Here the trick
is to start with the corner entries.

44 13 9 15 71 67 5 8 29

In this case, both entries are on the wrong side. Thus we swap them and get

8 13 9 15 71 67 5 44 29

Now we repeat this procedure for the remaining entries: we zoom in until we find again two
bad entries. In this case,

8 13 9 15 71 67 5 44 29

and swap it:

8 13 9 15 5 67 71 44 29.
Eventually, the two lines meet and we are done: we only have to move the pivot element, which
is on the right most place, to the correct position, namely at the position where the two lines
meet:
8 13 9 15 5 29 71 44 67
Summarizing, we obtained our split: all elements which are smaller than 29 are left of it and
all elements which are large are right to it. In total, we needed n − 1 = 8 comparisons to obtain

9
this split. Note that the element 29 is already at the correct position of the to be sorted array.
Thus we have to repeat this tactic for the remaining sub-arrays. E.g., we obtain the following
splits (applying the method recursively and choosing particular pivot elements):

44 13 9 29 71 67 5 8 15
↓ 8 comparisons

8 13 9 15 5 29 71 44 67

↓ 4+2=6 comparisons

5 13 9 15 8 29 44 67 71

↓ 3 comparisons

5 8 9 15 13 29 44 67 71

↓ 1 comparison

5 8 9 13 15 29 44 67 71
Summarizing, we needed in total
8 + 6 + 3 + 1 = 18
comparisons to QuickSort the above array (with the particularly chosen pivot elements marked
with a box).
We recall that SelectionSort needs n(n−1)
2 n=9
= 9 · 4 = 36 comparisons. So there is an improve-
ment (as the name QuickSort suggests).
Note further that QuickSort strongly depends on the choice of the pivot elements. In particular,
one can construct, e.g., a worst case scenario as follows: Take an already sorted array and apply
QuickSort by choosing always the right most element. Then we obtain the worst split: the pivot
element is right most and all other elements are on the left-hand side. Thus QuickSort is applied
to n − 1 elements in the next step. Applying this argument iteratively, we need in this worst
case situation
n(n − 1)
(n − 1) + (n − 2) + (n − 3) + · · · + 1 =
2
comparisons. In other words: QuickSort behaves in the worst case like the slow algorithm
SelectionSort.
In order to see (and prove) the improvement of QuickSort in contrast to, e.g., SelectionSort, we
have to explore the average case. Here we assume that the pivot elements are chosen arbitrarily
and that after the split it is equally likely that the pivot element is at position 1, 2, . . . , n − 1
or n. Under this assumption, we are interested in the following counting:
F (n) = the avarage number of pairwise comparisons to quicksort n elements (n ≥ 0).
The base case of QuickSort is the empty array or an array of length 1. Here the array is already
sorted and no comparisons are necessary. Thus we have
F (0) = F (1) = 0.

10
For an array of length n = 2 QuickSort will perform exactly one comparison, i.e., we can set

F (2) = 1.

More generally, if we are given an array of length n, we choose a pivot element (at random)
and calculate in the divide step (of our Divide and Conquer strategy) a split. For this task we
need n − 1 comparisons (independently of the choice of the pivot element). By our assumption
it is equally likely that the pivot element will be at position 1, at position 2,..., or at position
n. Thus we get
n
1X
− 1} +
F (n) = |n {z Fk (n);
n k=1
comparisons
for the split
here Fk (n) denotes the average number of comparisons that are needed to sort the derived array
where k − 1 elements are left to the pivot element and n − k are right to the pivot element.
More precisely, Fk (n) is determined by the property that QuickSort is applied to each of the
two subarrays: namely, the average number of comparisons are F (k − 1) for the left array and
the average number of comparisons are F (n − k) for the right array. Thus we have

Fk (n) = F (k − 1) + F (n − k)

and in total we get

n
1X
F (n) = n − 1 + (F (k − 1) + F (n − k)), n≥1
n k=1

Note that this formula (together with F (0 = 0) allows us to compute all values of F (n). E.g.,
we compute

n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...
(1)
F (n) 0 0 1 83 29
6
37
5
103
10
472
35
2369
140
2593
126
30791
1260
32891
1155
452993
13860
476753
12870
499061
12012
...

Unfortunately, this formula (or the produced numbers) do not provide any information how
good QuickSort really is.
In a preprocessing step we simplify the found recurrence further. A first observation is that the
summand consists of two parts which are equal:
n n
k→n−k
X X
F (k − 1) = F (n − k).
k=1 k=1

11
Thus we get
n
1X
F (n) = n − 1 + (F (k − 1) + F (n − k))
n k=1
n n
1X X
=n−1+ (F (k − 1) + F (n − k))
n k=1 k=1
n
2X
=n−1+ F (k − 1)
n k=1
n−1
2X
=n−1+ F (k).
n k=0

Second, we eliminate the indefinite sum with upper bound n (where the summand itself is free
of n). This can be accomplished easily if the factor in front of the sum is also free of n. To
accomplish this latter requirement, we first multiply our recurrence with n and get
n−1
X
n F (n) = n(n − 1) + 2 F (k) n ≥ 1.
k=0

Given this special form, we shift the recurrence in n, i.e., replace n by n + 1 yielding (where
the constant in front of the sum does not change!)
n
X
(n + 1) F (n + 1) = (n + 1)n + 2 F (k) n ≥ 0
k=0

Finally, we subtract both and obtain

Xn n−1
X
(n + 1) F (n + 1) − nF (n) = 2n + 2 ( F (k) − F (k )) n ≥ 1.
|k=0 {z k=0
}
=F (n)

Summarizing, we obtained
(n + 1)F (n + 1) − (n + 2)F (n) = 2n, n≥1
with the initial value F (1) = 0. One can easily check that the found recurrence is also valid for
n = 0 with F (0) = F (1) = 0. Thus we obtain
(n + 1)F (n + 1) − (n + 2)F (n) = 2n, n≥0
(2)
F (0) = 0.
By construction this simplified recurrence produces again the sequence (F (n))n≥0 where the
first values are printed in (1). More precisely, we can use the formula
(
n+1
n
F (n − 1) + 2 n−1
n
if n ≥ 1
F (n) ←
0 if n = 0.

12
In the following we will explore its behavior further by solving the found recurrence. For first-
order linear recurrences (here F (n) and F (n + 1) arise linearly) we can exploit the following
method, also called “variation of constants”.
Step 1: Find a closed form for the homogeneous equation:

(n + 1)H(n + 1) − (n + 2)H(n) = 0.

Unrolling it and proper cancellations give

n+2 n+2 n+1
H(n + 1) = H(n) = · H(n − 1) = . . .
n+1 n+1 n
n+2  n
+1 n 3
2

=  · · . . . · H(0) = (n + 2)H(0),

n+1
 n
 n
 −1 2
1
and thus
H(n) = (n + 1)H(0).
Using the homogeneous solution (n + 1) (we ignore the constant H(0)), we make the following
ansatz in
Step 2: Find a sequence G(n) such that

F (n) = (n + 1)G(n)

holds for all n ≥ 0.

As a consequence it follows that
0 = F (0) = G(0)
and
=F (n+1) =F (n)
z }| { z }| {
(n + 1) (n + 2)G(n + 1) −(n + 2) (n + 1)G(n) = 2n, n≥0
⇕
2n
G(n + 1) − G(n) = , n ≥ 0.
(n + 1)(n + 2)
Using telescoping (see HW 3) it follows that
n−1
X 2k
G(n) − G(0) = , n≥0
| {z }
k=0
(k + 1)(k + 2)
=0

and with summation (HW 2) we get

4n
G(n) = 2Hn − , n ≥ 0. (3)
n+1
Thus
F (n) = (n + 1)G(n) = 2(n + 1)Hn − 4n, n ≥ 0. (4)
Finally, we show that the average number F (n) to quicksort n elements is asymptotically equal
to 2n log(n); as a consequence it also follows that F (n) ∈ O(n log(n)).

13
Theorem 1.11.
F (n) ∼ 2n log(n).

Proof. We have

F (n) = 2(n + 1)Hn − 4n

∼ 2(n + 1)Hn
∼ 2nHn
∼ 2n log(n).

The last equivalence follows by Hn ∼ log(n); see HW 7.

Example 1.12. For an array of length n = 100 SelectionSort needs n(n−1)

2
= 4950 comparisons
and QuickSort (in average) 2n log(n) = 921.03 comparisons; this looks not like a big deal.
However, if we take, e.g., n = 1000000, then SelectionSort needs ∼ 5 ∗ 1011 comparisons, and
QuickSort ∼ 2.7631 ∗ 107 comparison; so there is the speedup factor 18095.

Lecture from March 19, 2024

1.4 A case study for Binary Search Trees (BST)
Definition 1.13. A binary search tree is a binary tree where in each subtree with root x all the
elements in its left subtree are smaller and all elements in its right subtree are larger than x.

Example 1.14. The binary search tree

7 (5)
4 10

2 5 8 13

represents the set {2, 4, 5, 7, 8, 10, 13}. It can be generated by inserting step-wise the elements,
e.g., in the order 7 → 4 → 10 → 2 → 5 → 8 → 13:

7 → 7 → 7 → 7 → ...

4 4 10 4 10

2
In the tree (5) the paths P1 = (7), P2 = (7, 10), or P3 = (7, 4, 5) go from the root 7 to the root
7, to the inner node 10 or to the leaf 5 (via the inner node 4), respectively. P1 has path length
1, P2 has path length 2 and P3 has path length 3.

14
An alternative tree can be generated by inserting step-wise the elements in the order 2 → 4 →
5 → 7 → 8 → 10 → 13:
2
4
5

7
8
10

13.

In worst case a binary search tree turns to a linked list (see the second tree in the example).
Thus finding an element in such a worst case scenario requires n operations.
However, the average time complexity is much better in a randomly chosen tree. More precisely,
take the set S = {a1 , a2 , . . . , an } with a1 < a2 < · · · < an and suppose that we are given a
binary search trees in which the elements S are stored at random. This means that they are
generated by a certain order b1 → b2 → · · · → bn (with {a1 , a2 , . . . , an } = {b1 , b2 , . . . , bn })
where each insertion order b1 → b2 → · · · → bn is equally likely. E.g., the element b1 equals the
element a1 with probability 1/n, it equals a2 with probability 1/n, etc.
Now define

P (n) = the avarage path length of such a binary search tree with n nodes.

As illustrated in the above example a path starts at the root and walks down a tree and
stops at an inner node or a leaf; in particular, the path length is the number of nodes that
are visited during the walk (including the root). Then the average cost to find an element3
c ∈ S (randomly chosen) in a tree (randomly generated) equals precisely P (n): it is simply the
average path length (the path ends at c).
Similarly to the average number of operations F (n) in QuickSort, we will explore the average
number P (n) to find an element in a binary search tree. Obviously we have

P (1) = 1.

Next, consider the following special case: the first element that we insert in our random con-
struction is ai+1 where 0 ≤ i < n. After inserting randomly the remaining n − 1 elements we
obtain a tree with the following shape:

b1 = ai+1 (6)

T1 T2
3
It seems nonsense to search for an element in the tree if one assumes that it is in. However, c might be
a data base key and one is interested in extracting the data that is attached to c. Thus one has to find the
element c in the tree which is stored together with a pointer that refers to the desired data.

15
where the elements S1 = {a1 , . . . , ai } are stored in T1 and S2 = {ai+1 , . . . , an } are stored in T2 .
Now consider the average path length δai+1 from the root ai+1 to any node c randomly chosen
from S. Note that c = b1 = ai+1 has probability n1 , c ∈ S1 has probability ni , and c ∈ S2 has
probability n−i−1
n
. Thus we obtain three cases:
1
1. With probability n
the path length is 1 (we go from c = ai+1 to c).
2. With probability ni we obtain a path of at least length two. It start at ai+1 , goes to
another element in S1 and from this node the average path length is P (i) to end up at c.
Thus the average path length equals 1 + P (i).
n−i−1
3. Analogously to case 2, we obtain with probability n
the average path length 1+P (n−
i − 1).
In total it follows that
δai+1 = n1 + ni (P (i) + 1) + n−i−1
n
(P (n − i − 1) + 1)
i n−i−1
= 1 + n P (i) + n P (n − i − 1).
In order to get a complete formula (recursion for P (n)) we note that each special case (6) with
b1 = ai+1 for 0 ≤ i < n is equally likely, i.e., arises with probability n1 . Thus we get
n−1
X 1
P (n) = δai+1 .
i=0
n
HW 8. Show that
n−1
2 X
P (n) = 1 + i P (i).
n2 i=0
HW 9. Show that
n2 P (n) − (n − 1)(n + 1)P (n − 1) = 2n − 1, n ≥ 2.
HW 10. Solve the recurrence in closed form (i.e., in terms of the harmonic numbers). More
precisely, perform the following steps:
1. Compute a solution H(n) ∈ Q(n) of the homogeneous version
n2 H(n) − (n − 1)(n + 1)H(n − 1) = 0.

2. Make the ansatz P (n) = H(n)G(n) which leads to

G(n + 1) − G(n) = r(n) r≥l
for some r(n) ∈ Q(n) and l ∈ N. By the telescoping trick this gives
n−1
X
G(n) − G(l) = r(k)
k=l

with some explicitly given G(l) ∈ Q and thus

n−1
!
X
F (n) = H(n) r(k) + G(l) .
k=l

16
 3. Simplify the sum further in term of the harmonic numbers.

Theorem 1.15.

P (n) ∈ O(log(n)),
P (n) ∼ 2 log(n).

Proof. HW 11.

Summarizing, given an arbitrary binary search tree with n elements, one finds an element (that
occurs in the tree) in O(log(n)) operations. A similar result can be derived for the case that
the element is not stored and one wants to verify this fact.

17
2 ∗ Recall: basic notions from algebra
In the following we repeat some basic notions and constructions from algebra that will arise in
the lecture. In particular, they are useful to tackle the bonus problems stated below.

Recall 2.1. Let A be a set with two operations + : A × A → A and · : A × A → A.

(A, +, ·) is called a field if the following properties hold:

1. ∀a, b, c ∈ A : (a + b) + c = a + (b + c);

2. ∀a, b ∈ A : a + b = b + a;

3. ∃0 ∈ A ∀a ∈ A : 0 + a = a;

4. ∀a ∈ A ∃b ∈ A : a + b = 0;

5. ∀a, b, c ∈ A : (a · b) · c = a · (b · c);

6. ∀a, b ∈ A : a · b = b · a;

7. ∃1 ∈ A \ {0} ∀a ∈ A : 1 a = a;

8. ∀a ∈ A \ {0} ∃b ∈ A \ {0} : a b = 1;

9. ∀a, b, c ∈ A : a · (b + c) = a · b + a · c.

If the operations are clear from the context, one simply writes A for the field. Often one neglects
· and simply writes a b instead of a · b.

Note: Properties (1)–(4) imply that (A, +) is a commutative (abelian) group, and properties
(5)–(8) imply that also (A \ {0}, ·) is a commutative (abelian) group. Finally, property (9)
states that the operations + and · interact distributively.

Example 2.2. The rational numbers (Q, +, ·), the real numbers (R, +, ·) or the complex num-
bers the real numbers (C, +, ·) are fields with the usual operations. Furthermore, the set of
rational functions (Q(n), +, ·), (R(n), +, ·) or (C(n), +, ·) (see BPs 1 and 2) form fields with the
usual operations.

Often one is given algebraic structures which are equipped with operations that do not satisfy
all the properties required for a field. In this lecture we deal mostly with commutative rings
with 1.

Recall 2.3. Let A be a set with two operations + : A × A → A and · : A × A → A.

(A, +, ·) is called a commutative ring with 1 if the properties (1)–(7) and (9) from Recall 2.1
hold. If the operations are clear from the context, one simply writes A for the ring.

Note: a commutative ring with 1 is a field if all non-zero elements are invertible (i.e., property
(8) in Recall 2.1 holds). In general, one can distinguish two types of rings.

18
Recall 2.4. A commutative ring A with 1 is called integral domain if the following holds:

∀a, b ∈ A : a · b = 0 ⇒ a = 0 ∨ b = 0.

If the ring is not an integral domain, one finds two such elements a, b ∈ A \ {0} with a · b = 0.
Such elements are also called zero-divisors. In this case, A is also called a a commutative ring
with 1 and zero-divisors.

Note that a commutative ring with 1 which contains zero-divisors cannot be a field. Contrary,
an integral domain (i.e., a commutative ring with 1 and without zero-divisors) might be a field.
Even better, if it is an integral domain but not a field yet, one can build the set of quotients.
Then this extended set forms a field and contains A as subring. More precisely, one can carry
out the following construction.

Recall 2.5. Let (A, +, ·) be an integral domain and define the set of quotients
na o
Q(A) = a ∈ A, b ∈ A \ {0} .
b
Since A is an integral domain, it follows that for any b1 , b2 ∈ A \ {0} we have b1 · b2 ̸= 0. Thus
we can define the operation ⊕ : Q(A) × Q(A) → Q(A) defined by

a1 a2 a1 · b 2 + a2 · b 1
⊕ = (7)
b1 b2 b1 · b2

and the operation ⊙ : Q(A) × Q(A) → Q(A) defined by

a1 a2 a1 · a2
⊙ = . (8)
b1 b2 b2 · b2
One can verify that (Q(A), ⊕, ⊙) is a field (i.e., all 9 properties in Recall 2.1 hold). Q(A) is
also called the quotient field of A. Note that A is contained in Q(A) by identifying a ∈ A with
a
1
∈ Q(A). In particular, for any a, b ∈ A we have a ⊕ b = a + b and a ⊙ b = a · b. This
means that the ring A is contained in the field Q(A). Usually, one reuses for Q(A) again the
operations + and · from the integral domain A.

Example 2.6. The set of integers Z forms a ring with the usual addition and multiplication.
The ring is an integral domain, i.e., for any a, b ∈ Z \ {0} we have a · b ̸= 0. The set of quotients
Q(Z) is nothing else than Q. Together with the operations (7) and (8) one obtains a field, also
called the field of rational numbers. Obviously, Z is contained in Q by identifying a1 ∈ Q with
a ∈ Z.
A ring with zero divisors cannot be turned to a field: one can find at least two denominators
whose multiplication turns to zero. Such “exotic” rings will arise in the next section.

Sometimes one is faced with a commutative (abelian) group (A, +), i.e., with an operation
+ : A × A → A with the properties (1)-(4) from Recall 2.1, but a multiplication · : A × A → A
with the properties of a ring or a field does not exist. However, in many cases one can determine
a field K together with a scalar operation ∗ : K × A → A yielding a vector space.

19
Recall 2.7. Let (K, +, ·) be field and let A be a set with two operations + : A × A → A and
∗ : K × A → A.
(A, +, ∗) is called a vector space over K if properties (1)–(4) from Recall 2.1 hold and in addition
the following properties hold:

1. ∀a ∈ A ∀λ, µ ∈ K : (λ · µ) ∗ a = λ ∗ (µ ∗ a);

2. ∀a ∈ A : 1 ∗ a = a (here 1 is the neutral element in K);

3. ∀a, b ∈ A ∀λ ∈ K : λ ∗ (a + b) = λ ∗ a + λ ∗ b;

4. ∀a ∈ A ∀λ, µ ∈ K : (λ + µ) ∗ a = λ ∗ a + µ ∗ a.

∗ is also called a scalar multiplication.

Example 2.8. R3 is a vector space over R. E.g.,

(1, 0, 0) + (−1) ∗ (0, 1, 0) = (1, 0, 0) + (0, −1, 0) = (1, −1, 0).

More generally take any field K and n ∈ N∗ . Then Kn (the set of vectors of length n with
entries from K) forms a vector space over K.

20
Lecture from April 9, 2024

3 Generating functions and formal power series

In this lecture we will often deal with sequences (an )≥0 (see, e.g., (1) with an = F (n)). As we
will see later, it is often more convenient to work with a generating function
∞
X
(an )n≥0 7→ an x n .
n=0

For instance, the generating function of an = 1 with n ≥ 0 yields

∞
X 1
(an )n≥0 7→ xn = . (GS)
n=0
1−x

In analysis the identity (GS) can be interpreted as follows by considering the functions

• f : R \ {1} → R defined by f (x) = 1

1−x
;

• g : (−1, 1) → R defined by g(x) = limN →∞

PN
n=0 xn ; by the ratio test the power series
g(x) has the convergence radius r = 1.

Then (GS) in analysis means

g(x) = f (x) ∀x ∈ (−1, 1).

In algebra the interpretation will be elaborated in Example 3.12 below.

Definition 3.1. (including notations)
K denotes a field containing the rational numbers Q as subfield; typical examples are K = Q, the
n3 +1
rational function field K = Q(n) with rational coefficients (like 2n 2 +3 ), K = R or the rational
3
√
function field K = R(n) with real coefficients (like n2n+2 +π2 ).
The set of sequences with entries from K is denoted by

KN := {(an )n≥0 | an ∈ K}.

In the following we will explore step-wise more and more operations that can be applied to the
set KN . We start with the following simple versions.
Definition 3.2. For (an )n≥0 , (bn )n≥0 ∈ KN and λ ∈ K we define

(an )n≥0 + (bn )n≥0 := (an + bn )n≥0 ,

λ ∗ (an )n≥0 := (λan )n≥0 .

Example 3.3. We have

(1, 0, 0, 0, . . . ) + (−1) ∗ (0, 1, 0, 0, . . . ) = (1, 0, 0, 0, . . . ) + (0, −1, 0, 0, . . . ) = (1, −1, 0, 0, . . . ).

21
Lemma 3.4. (KN , +, ∗) is a vector space over K.

Proof. BP 3.

Remark 3.5. For m ∈ N∗ set

K̃m = {(an )n≥0 ∈ KN | al = 0 ∀l ≥ m}.

Then K̃m and Km are isomorphic as vector spaces, i.e., up to renaming of the objects (taking
only the first m entries from each element of K̃m )

(a0 , a1 , . . . , am−1 , 0, 0, 0, . . . ) 7→ (a0 , a1 , . . . , am−1 )

they are the same. Summarizing, the vector space KN contains K̃m and thus Km as a special
case (Km is the well known vector space known from linear algebra; it is a subspace of KN ).

Example 3.6. For K = R and m = 3 we conclude that

R̃3 = {(an )n≥0 ∈ RN | al = 0 ∀l ≥ 3}

and R3 are isomorphic. For instance, we identify (1, −1, 0, 0, . . . ) ∈ R̃3 with (1, −1, 0) ∈ R3 .

In contrast to the scalar multiplication ∗ for KN , one can define more flexible operations for
KN . As will be seen later, the Cauchy product can be considered as a generalization of the
scalar multiplication.

Definition 3.7. For (an )n≥0 , (bn )n≥0 ∈ KN we define the Hadamard product ⊙ : KN ×KN → KN
by

(an )n≥0 ⊙ (bn )n≥0 := (an bn )n≥0

and the Cauchy product · : KN × KN → KN by

(an )n≥0 · (bn )n≥0 := (cn )n≥0

where n
X
cn = ak bn−k .
k=0

Example 3.8. Consider (an )n≥0 with an = 1 for n ≥ 0 and (bn )n≥0 with b0 = 1, b1 = −1 and
bn = 0 for n ≥ 2. Then

(an )n≥0 ⊙ (bn )n≥0 = (1, 1, 1, 1, . . . ) ⊙ (1, −1, 0, 0, . . . ) = (1, −1, 0, 0, . . . )

and
(an )n≥0 · (bn )n≥0 = (1, 1, 1, 1, . . . ) · (1, −1, 0, 0, . . . ) = (c0 , c1 , c2 , . . . )
with n
X
cn = ak bn−k .
k=0

22
More precisely,
c0 = 1 · 1 = 1
c1 = a0 b1 + a1 b0 = −1 + 1 = 0
c2 = a0 b2 + a1 b1 + a2 b0 = 0 + −1 + 1 = 0
c 3 = a1 b 3 + a1 b 2 + a2 b 1 + a3 b 0 = 0 + 0 − 1 + 1 = 0
..
.
cl = 0 ∀l ≥ 1.
Thus
(an )n≥0 · (bn )n≥0 = (1, 1, 1, 1, . . . ) · (1, −1, 0, 0, . . . ) = (1, 0, 0, 0, . . . ). (9)
Theorem 3.9. (KN , +, ⊙) is a commutative ring with4 1, but not an integral domain.

Proof. BP 4.

Recall: A ring R with 1 is an integral domain if

∀a, b ∈ R : a · b = 0 ⇒ a = 0 ∨ b = 0
If there are two elements a, b ∈ R with a ̸= 0 ̸= b and a b = 0, then and a and b are called zero
divisors. Obviously, R is an integral domain if and only if it has no zero-divisors.
Example 3.10. (KN , +, ⊙) contains zero-divisors: (an )n≥0 = (1, 0, 1, 0, 1, 0, . . . ) and (bn )n≥0 =
(0, 1, 0, 1, 0, 1, . . . ) are not the zero-sequence but their Hadamard product produces the zero-
sequence:
(an )n≥0 ⊙ (bn )n≥0 = (1, 0, 1, 0, 1, 0, . . . ) ⊙ (0, 1, 0, 1, 0, 1, . . . ) = (0, 0, 0, 0, 0, . . . ).
Theorem 3.11. (KN , +, ·) is a commutative ring with5 1, it is even an integral domain.

Proof. BP 5: Show that (KN , +, ·) is a commutative ring with 1.

HW 12: Show that it is even an integral domain6 .

Notation. For (an )n≥0 ∈ KN we also write

∞
X
(an )n≥0 =: an xn = a(x)
n=0

with x an indeterminate (variable).

For (KN , +, ·) we shall write (K[[x]], +, ·) or K[[x]] for short and will call it also the ring of
formal power series over K.
Note: (1, 0, 0, 0, . . . ) = 1 x0 + 0 x1 + 0 x2 + 0 x3 + · · · = 1 is the 1-element in K[[x]]. If it is
clear from the context, we simply write a b instead of a · b.
4
Note: (0, 0, 0, . . . ) is the zero element and (1, 1, 1, 1, . . . ) is the 1 element.
5
Note: (0, 0, 0, . . . ) is the zero element and (1, 0, 0, 0, . . . ) is the 1 element.
6
Hint: To prove that the ring is integral, we show that it has no zero divisors. Namely, suppose that (an )n≥0
and (bn )n≥0 are both not the zero-sequence (as warm up example suppose that a0 ̸= 0 ̸= b0 ). Then show that
at least one entry in (an )n≥0 · (bn )n≥0 is not zero.

23
Example 3.12. Rewriting (9) in its formal power series notation gives
∞
!
X
xn (1 − x) = 1.
n=0

algebra sense means that 1 − x and ∞ n

P
In summary, the interpretation of (GS) in theP n=0 x are
∞ n
the multiplicative inverses to each other, i.e., n=0 x multiplied by 1 − x equals the 1-element.
In short,
∞
−1 1 X
(1 − x) = = xn .
1 − x n=0
Remark 3.13. We define
nX∞ o
K[x] = an xn ∈ K[[x]] | ak = 0 for all k ≥ δ for some δ ∈ N ⊆ K[[x]]
n=0
Pm1 n
and
Pm2 call it the set of polynomials. Take two such polynomials a(x) = n=0 an x and b(x) =
n
n=0 bn x from K[x] (we define ak = 0 for k > m1 and bk = 0 for k > m2 ). Then the Cauchy
product simplifies to
mX
1 +m2

a(x) · b(x) = cn x n
n=0
Pn
with cn = k=0 ak bn−k . In Mathematica the multiplication a(x), b(x) ∈ Q[x] can be carried out,
e.g., by Expand[a*b]. Note that (K[x], +, ·) itself is a ring with 1 ∈ K[x] called the polynomial
ring over K. This follows from the fact that for all a, b ∈ K[x] we have that a + b ∈ K[x]
and a · b ∈ K[x] i.e., (K[x], +, ·) is a subring of (K[[x]], +, ·). Furthermore, since K[[x]] has no
zero divisors, also its subset K[x] has no zero-divisors. In other words, (K[x], +, ·) itself is an
integral domain.
Remark 3.14. Take λ ∈ K ⊆ K[[x]] and b(x) = ∞ n
P
n=0 bn x ∈ K[[x]] and consider the Cauchy
product
λ · b(x) := (λ, 0, 0, . . . ) · (b0 , b1 , b2 , . . . ) = (cn )n≥0
with n
X
cn = ak bn−k
k=0
with a0 = λ and al = 0 for l ≥ 1. Then cn = λ bn and hence
∞
X
λ · b(x) = (λb0 , λb1 , λb2 , . . . ) = (λ bn )xn .
n=0

In other words, restricting · : K[[x]] × K[[x]] → K[[x]] to · : K × K[[x]] → K[[x]] yields precisely
our scalar multiplication ∗ : K × K[[x]] → K introduced in Definition 3.2 and by Lemma 3.4 it
follows that (K[[x]], +, ·) with · : K × K[[x]] → K[[x]] is a vector space over K.
Lemma 3.15. Take λ ∈ K, m ∈ N and a(x) = ∞ n
P
n=0 an x ∈ K[[x]]. Then
∞
! ∞ ∞
X X X
m n n+m
(λ x ) · an x = λan x = λan−m xn .
n=0 n=0 n=m

24
Proof. HW 13.
Definition 3.16. (coefficient functional)
For k ∈ N we define
∞
X
k
[x ] an x n = ak .
n=0

As shortcut we write
a(0) := [x0 ]a(x) = a0 .
Lemma 3.17. For k ∈ N and a(x), b(x) ∈ K[[x]],

[xk ](a(x) + b(x)) = [xk ]a(x) + [xk ]b(x),

[xk ](λ a(x)) = λ[xk ]a(x).

Proof. HW 14.

Lecture from April 16, 2024

Remark 3.18. By the properties from Lemma 3.17 it follows that for a fixed k ∈ N the map

[xk ] : K[[x]] → K

is a linear map.
HW 15. In (K[x], +, ·) prove

1. ( ∞ n n
P
n=0 c x ) (1 − cx) = 1 (c ∈ K)

P∞ 1 n
P∞ (−1)n n 
2. n=0 n! x k=0 n! x = 1.

Definition 3.19. Let R be a commutative ring with 1 containing Q. For r ∈ R and k ∈ N we

define the falling factorial

rk = r(r − 1)(r − 2) · · · (r − k + 1), k≥1

r0 = 1

and the raising factorial

rk̄ = r(r + 1)(r + 2) · · · (r + k − 1), k≥1

r0̄ = 1.

In addition, for r ∈ R and k ∈ Z we define the binomial coefficient with

( k
r
 
r k≥0
:= k!
k 0 k < 0.

25
HW 16. Show for all z ∈ C and k ∈ Z that
     
z+1 z z
= + .
k k k−1

Definition 3.20. The following formal power series deserve a short-cut notation:
∞
X 1 n
exp(x) := x ∈ K[[x]],
n=0
n!
∞
X (−1)n
exp(−x) := xn ∈ K[[x]],
n=0
n!
∞
X (−1)n+1 n
log(1 + x) := x ∈ K[[x]],
n=1
n
∞
X 1 n
log(1 − x) := − x ∈ K[[x]].
n=1
n

Remark 3.21. From HW 15 we know that

exp(x) · exp(−x) = 1,

i.e., exp(−x) is the multiplicative inverse of exp(x):

exp(x)−1 := exp(−x).

Remark 3.22. In analysis we know that

∞ ∞
d X 1 n−1 X 1
log(1 − x) = − nx =− xn−1 = −
dx n=1
n n=1
1−x

with |x| < 1.

The last two remarks motivate us to consider the operations differentiation and division also
in our formal ring K[[x]] in more details.

3.1 Differentiation and division

Definition 3.23. Let (R, +, ·) be a commutative ring with 1 (containing Q as a subring). Let
D : R → R be a function such that

D(a + b) = D(a) + D(b)

D(a · b) = D(a) · b + a · D(b)

for all a, b ∈ R. Then D is called a (formal) derivative on R, and the pair (R, D) is called a
differential ring.

26
Lemma 3.24. Consider Dx : K[[x]] → K[[x]] with
∞
X  ∞
X
k
Dx an x = an+1 (n + 1)xn .
n=0 n=0

Then (K[[x]], Dx ) is a differential ring.

Proof. HW 17.
Example 3.25.
∞ ∞ ∞
X 1 n X 1 n
X 1
Dx x = (n + 1)x = .
n=0
n! n=0
(n + 1)! n=0
n!
This motivates the notation from above: for exp(x) := ∞ 1 n
P
n=0 n! x we have Dx exp(x) = exp(x).
R
Definition 3.26. We define the formal integration x : K[[x]] → K[[x]] by
Z X ∞ ∞
n
X an−1 n
an x 7→ x .
x n=0 n=1
n
Remark 3.27. In analysis this formal integration is equivalent to the integration of a power
series from 0 to x.
R
The action of Dx and x on the sequence representation of a formal power series is nothing else
than the shift of the sequence (up to some normalizing factor) to the left or right:
Dx (a0 , a1 , a2 , a3 , . . . ) = (1 a1 , 2 a2 , 3 a3 , . . . )
Z
(a0 , a1 , a2 , . . . ) = (0, a10 , a21 , a32 , . . . ).
x

This yields
Theorem R 3.28. For all a(x) ∈ K[[x]] we have
1. D
R x x a(x) = a(x) “Fundamental Theorem of Calculus I”
2. x Dx a(x) = a(x) − a(0) “Fundamental Theorem of Calculus II”
3. [xn ]a(x) = n!1 ((Dx )n a(x)) |x=0 “Taylor’s formula”
Proof. With Z
Dx (a0 , a1 , a2 , . . . ) = Dx (0, a10 , a21 , a32 , . . . ) = (a0 , a1 , a3 , . . . )
x
property 1 follows. With
Z Z
Dx (a0 , a1 , a2 , a3 , . . . ) = (1 a1 , 2 a2 , 3 a3 , . . . ) = (0, a1 , a2 , a3 , . . . )
x x

and
a(x) = (a0 , a1 , a2 , a3 , . . . ) =(a0 , 0, 0, 0, . . . ) + (0, a1 , a2 , a3 , . . . )
Z
= (a0 , 0, 0, 0, . . . ) + Dx (a0 , a1 , a2 , a3 , . . . )
Z x

= a(0) + Dx a(x)
x

27
property 2 is established. Finally, observe that
(Dx )n (a0 , a1 , a2 , a3 , a4 , a5 , . . . ) = (Dx )n−1 Dx (a0 , a1 , a2 , a3 , a4 , a5 , . . . )
= (Dx )n−1 (1 a1 , 2 a2 , 3 a3 , 4 a4 , 5 a5 , . . . )
= (Dx )n−2 Dx (1 a1 , 2 a2 , 3 a3 , 4 a4 , 5 a5 , . . . )
= (Dx )n−2 (1 · 2 a2 , 2 · 3 a3 , 3 · 4 a4 , 4 · 5 a5 . . . )
= (Dx )n−3 Dx (1 · 2 a2 , 2 · 3 a3 , 3 · 4 a4 , 4 · 5 a5 . . . )
= (Dx )n−3 (1 · 2 · 3 a3 , 2 · 3 · 4 a4 , 3 · 4 · 5 a5 , . . . )
= · · · = (n!an , n! a , n! a , n! a , . . . )
1! n+1 2! n+2 3! n+3

which gives (Dx )n (a0 , a1 , a2 , a3 , . . . )|x=0 = n!an = n![xn ]a(x), and thus proves property 3.

The following property is particular strong: one can invert a formal power series if and only if
the constant term does not vanish.
Theorem 3.29. [multiplicative inverse] Let a(x) ∈ K[[x]]. Then:

There exists a b(x) ∈ K[[x]] with a(x) · b(x) = 1 ⇔ a(0) ̸= 0 .

Proof. Let a(x) = ∞ n

P
n=0 an x .
⇒: Suppose that there is a b(x) = ∞ n
P
n=0 bn x with

a(x) · b(x) = 1.
Then by the definition of the Cauchy product,
a0 b 0 = 1
and thus, since K is a field, a(0) = a0 ̸= 0.
⇐ Suppose that a0 ̸= 0. We construct b(x) = bn xn such that
∞
! ∞
! ∞ n
X X X X
0 1 2 n n n
1 x + 0 x + 0 x + · · · = 1 = a(x) · b(x) = an x · bn x = x ak bn−k . (10)
n=0 n=0 n=0 k=0

By coefficient comparison in equation (10) at [x0 ] we get a0 b0 = 1 and thus with a0 ̸= 0 we get
(in the field K)
1
b0 = , (11)
a0
i.e., b0 is determined. Furthermore, by coefficient comparison in equation (10) at [xn ] with
n ≥ 1 we get
Xn Xn
0= ak bn−k = a0 bn + ak bn−k
k=0 k=1
and hence
n
1 X
bn = − ak bn−k . (12)
a0 k=1

Summarizing,

28
 • given a0 , we can determine b0 with (11),

• given a0 , a1 and b0 we can use the formula in (12) to determine b1 ,

• given a0 , a1 , a2 and b0 , b1 , we can use the formula in (12) to determine b2 ,

• ...
P∞
and thus all bn can be determined iteratively for a(x) = n=0 an x n .

Lecture from April 23, 2024

Note 1: If the standard operations in K are computable and if the coefficients a0 , a1 , . . . , al
(a0 ̸= 0) are given explicitly (can be computed by an algorithm), also the first coefficients
b0 , b1 , . . . , bl (b0 ̸= 0) can be computed. In particular, we get
l
! l
!
X X
al + · · · + 0 x}l +cl+1 xl+1 + cl+2 xl+2
bl = 1 + 0| x1 + 0 x2{z
n=0 n=0 =0

where cl+1 , cl+2 , . . . are error terms (which arise since we only considered the first l+1 coefficients
of a(x) and b(x)).
Note 2: Let b(x), b̃(x) ∈ K[[x]] such that

a(x) · b(x) = 1 = a(x) · b̃(x).

Then b(x) · (a(x) · b(x)) = b(x) · (a(x) · b̃(x)) and thus

b(x) = (a(x) · b(x)) · b(x) = (b(x) · a(x)) · b(x)

= b(x) · (a(x) · b(x)) = b(x) · (a(x) · b̃(x))
= (b(x) · a(x)) · b̃(x) = (a(x) · b(x)) · b̃(x) = b̃(x),

i.e., b(x) = b̃(x). Consequently, if a(x) has a multiplicative inverse b(x) (i.e., if a(x) ̸= 0), then
it is unique and motivates the following notation.
Notation. Let a(x) ∈ K[[x]] with a(0) ̸= 0. Then for the multiplicative inverse b(x) ∈ K[[x]]
of a(x) (determined, e.g., by the above theorem) we also write
1
a−1 (x) := b(x) or := b(x).
a(x)
P∞ P∞
Example. We have (1 − x) · n=0 xn = 1, i.e., the multiplicative inverse of 1 − x is n=0 xn
and we write ∞
−1 1 X
(1 − x) = = xn .
1 − x n=0

29
 P∞
Furthermore, the multiplicative inverse of n=0 xn is (1 − x) and we write

∞
!−1
X
n 1
x = P∞ = 1 − x.
n=0 n=0 xn

Example. By HW. 15 we have exp(x) · exp(−x) = 1. Thus exp(−x) is the multiplicative

inverse of exp(x), i.e.,
1
exp(x)−1 = = exp(−x);
exp(x)
furthermore, exp(x) is the multiplicative inverse of exp(−x), i.e.,
1
exp(−x)−1 = = exp(x).
exp(−x)
P∞ cn n
HW 18. Let exp(c x) := n=0 n! x . For a, b ∈ K show:

exp(a x) exp(b x) = exp((a + b)x).

Hint for possible solutions of the HWs below: Compute the first coefficients bn and use Sloan’s
database [Link] to find a closed form.

HW 19. Find a closed form for the coefficients in the multiplicative inverse of (1−2x)2 ∈ K[[x]].

HW 20. Find a closed form for the coefficients in the multiplicative inverse of (1−x)3 ∈ K[[x]].

HW 21. Find a closed form for the coefficients in the multiplicative inverse of exp(2x) ∈ K[[x]].

3.2 Finding closed forms for generating functions

Example Find a closed form for
∞
X
H(x) = Hn xn ∈ K[[x]]
n=0

where Hn denote the harmonic numbers (H0 = 0).

TACTIC: Find a (functional) equation for H(x).

A) by using the recurrence for Hn :

1
Hn+1 = Hn +
n+1

30
with H0 = 0.
Note: we stay in K[[x]] (no analysis!)
Using the recurrence (in the second line) we get
∞
X ∞
X ∞
X
n n
H(x) = Hn x = Hn x = Hn+1 xn+1
n=0 n=1 n=0
∞  
X 1
= Hn + xn+1
n=0
n+1
∞ ∞
X X xn+1 n
=x Hn x +
n=0 n=0
n+1
= xH(x) − log(1 − x)

and thus
1
H(x) = − log(1 − x). (13)
1−x
1
Note 1: Here we use that (1 − x) 1−x = 1.
1
Note 2: We consider − 1−x log(1 − x) as a closed form for H(x) since it is the product of well
known formal power series which we gave already special names:
P∞
• the geometric series 1
1−x
= n=0 xn ;
P∞ xn
• the logarithmic power series log(1 − x) = − n=1 n ; see also Definition 3.20.

B) by using an extra lemma (which we will use later again)

Lemma 3.30. We have7

∞ n
! ∞
X
n
X 1 X
x ak = an x n
n=0 k=0
1 − x n=0
or equivalently (by multiplying with 1 − x)
∞ n
! ∞
X X X
n
(1 − x) x ak = an x n .
n=0 k=0 n=0
7 1
P∞
The Cauchy product of 1−x with a formal power series a(x) = n=0 an xn yields a formal power series
Pn
whose coefficients are k=0 ak .

31
Proof.
∞ n
!
X X
LHS = (1 − x) xn ak
n=0 k=0
∞ n
! ∞ n
!
X X X X
= xn ak − xn+1 ak
n=0 n=0
| {zk=0 }! | {z k=0 }
∞
X n
X ∞ n−1
!
x0 a0 + xn
X X
ak xn ak
n=1 k=0 n=1 k=0
 
∞
X
 n n−1 
X n
X 
= x 0 a0 + x 
 a k − a k


n=1  k=0 k=0 
| {z }
an
∞
X
= an xn = RHS.
n=0

Remark: The special case of the above lemma with

(
1 if k = 0
ak =
0 if k ≥ 1

gives
∞
X
(1 − x) xn = 1.
n=0

Another special case can be used for H(x):

∞ n
(
X X 0 if k = 0
H(x) = xn ak where ak = 1
n=0 k=0 k
if k ≥ 1
∞
1 X
= an x n
1−x n=0
∞
1  X xn 
= 0+
1−x n=1
n
1
=− log(1 − x).
1−x
1
HW 22. Consider the formal power series f (x) = (1−x) 2 log(1 − x) ∈ Q[[x]]. Express the
P∞ n
coefficients fn ∈ Q of f (x) = k=0 fn x in terms of the harmonic numbers Hn .

32
4 Application: binary trees
We will apply the tools from the previous section in order to explore binary trees.
Definition 4.1. A binary tree is

• a single external node (denoted by □)

• or an internal node (denoted by •) that is connected to two binary trees: a left and a right
subtree.

To warm up, we consider all trees with n external nodes for n = 1, 2, 3, 4.

For n = 1 we get:

□
t0

For n = 2 we get:

•
□ □
t1 = t0 t0

For n = 3 we get:

• •
□ • • □

□ □ □ □
t2 = t0 t1 + t1 t0

And for n = 4 we get:

• • • • •

□ • □ • • • • □ • □
□ • • □ □ □ □ □ • □ □ •
□ □ □ □ □ □ □ □
t3 = t0 t2 + t1 t1 + t2 t0

In the following we want to explore

tn := the number of binary trees with n + 1 external nodes.

Looking at the above enumeration we get

n 0 1 2 3 ... n ...
tn 1 1 2 5 . . . ? ...

33
The main goal is to produce a general formula for tn . Note that we can produce all trees with
n + 1 external nodes by considering all trees of the form

•
a binary a binary
tree with k + 1 tree with n − k
external nodes external nodes

with k = 0, 1, 2, . . . , n − 1. Summarizing, we get

t0 = 1
n−1
X (14)
tn = tk tn−k−1 .
k=0

For instance,

t1 = t0 t0 = 1
t2 = t0 t1 + t1 t0 = 1 + 1 = 2
t3 = t0 t2 + t1 t1 + t2 t0 = 2 + 1 + 2 = 5;

note that this formula is also reflected in the graphical enumeration from above.
In general, we can now calculate any value tn with n ∈ N using this recursion formula. But we
can do much better!
After this preparation step we can activate our formal power series engine by defining the
generating function
X∞
t(x) = tn xn ∈ Q[[x]].
n=0

Hence
∞
X n−1
X
0 n
t(x) = t0 x + x tk tn−1−k
n=1 k=0
∞
X n
X
=1+ xn+1 tk tn−k
n=0 k=0
X∞ Xn
=1+x xn tk tn−k
n=0 k=0

and by the Cauchy product we get

= 1 + x t(x)2 .

Summarizing, we obtain the following functional equation:

x t(x)2 − t(x) + 1 = 0. (15)

34
As it turns out, the following trick makes our life easier: multiply the equation with x. This
gives
x2 t(x)2 − x t(x) + x = 0.
Thus if we define
T (x) := x t(x) ∈ Q[[x]]
we get
T (x)2 − T (x) + x = 0
||
1 2
T (x)2 − 2T (x) · 12 + − 41 + x


2
| {z }
1 2


= T (x)−
2

which is equivalent to
(T (x) − 12 )2 = 14 (1 − 4x).
⇕
(2T (x) − 1)2 = 1 − 4x.

Lemma 4.2. Let g(x) ∈ K[[x]] with g(0) = 1. Then there is a unique f (x) ∈ K[[x]] with
f (x)2 = g(x) and f (0) = 1. In addition, there is exactly one other solution which is −f (x).

Proof. HW 23 (Hint: adapt the proof of Theorem 3.29).

Lecture from April 30, 2024

With this lemma it follows that we can take f (x) ∈ K[[x]] with f (0) = 1 such that

f (x)2 = 1 − 4x. (16)

In particular, we get
2T (x) − 1 = ±f (x)
⇕
1 1
T (x) = ± f (x).
2 2
In the following we will write for the unique f (x) ∈ Q[[x]] with f (0) = 1 and f (x)2 = 1 − 4x
also √
1 − 4x := f (x).
Thus we get
1 1√
T (x) = ± 1 − 4x;
2 2
Looking at the constant term on both sides shows that
1 1√
T (x) = − 1 − 4x;
2 2
35
 √
the plus version would have given [x0 ]( 12 + 12 1 − 4x) = 1, but we have [x0 ]T (x) = 0.
√
Note that the formal power series 1 − 4x (which can be determined by the above lemma) has
a nice closed form. In the moment we present it without a proof and keep it as
Conjecture A (for a proof see later)
∞ 1
√ X
1 − 4x = 2 (−1)n 4n xn ∈ Q[[x]].
n=0
n

Suppose that our conjecture is correct. Then we can continue as follows:

∞
X 1 1 1√
tn xn = t(x) = ( − 1 − 4x) (17)
n=0
x 2 2
∞  
1 −1 X 12
= (−1)n 4n xn
x 2 n=1 n
∞  
1 X 12
=− (−1)n 4n xn−1
2 n=1 n

Warning: In (17) we divided by x which is not allowed in Q[[x]]. Formal details will come
later. Here we can justify it (somehow) since the constant term vanishes and thus the division
is possible by shifting the formal power series (considered as a sequence in QN ) to the left.
Consequently,
 1 
1
tn = − 2 (−1)n+1 4n+1
2 n+1
 
HW 24 1 2n
=
n+1 n

holds for all n ∈ N. Summarizing we obtain

Conjecture B
 
1 2n
tn =
n+1 n

Remark: Conjecture B would turn to a theorem if Conjecture A is verified. Conversely, if

Conjecture B can be verified, also Conjecture A is true since we can trace back the consequences.
In other words, verifying Conjecture A or B would give the full result.
In the following we verify Conjecture B (which also shows that Conjecture A holds).
Proof of Conjecture B with symbolic summation. Define
 
1 2n
sn = .
n+1 n

36
Then sn counts the number of trees with n + 1 external nodes if and only if it satisfies the old
recurrence (14), i.e., if and only if we have8

s0 = 1
n−1
X
sn = sk sn−k−1 .
k=0

Obviously s0 = 1 holds. What remains to verify is the second equation which reads as follows:
  X n−1    
1 2n 1 2k 1 2n − 2k − 2
= . (18)
n+1 n k=0
k+1 k n−k n−k−1

We verify this identity with the help of the summation package9 Sigma. First, we load it into
Mathematica:
In[1]:= << Sigma.m
Sigma - A summation package by Carsten Schneider © RISC-JKU

Next we insert the sum on the right-hand side of (18) into Mathematica. Note that we consider
even a more general sum by choosing the upper summation bound to be A (and not the special
value n − 1):
In[2]:= mySum = SigmaSum[1/(k + 1)SigmaBinomial[2k, k]/(n − k)SigmaBinomial[2n − 2k − 2, n − k − 1], {k, 0, A}]
A 2k
−2−2k+2n

−1−k+n
X k
Out[2]=
k=0
(1 + k)(−k + n)

Finally, we apply the function call SigmaReduce to the sum and obtain the following simplifi-
cation:
In[3]:=sol = SigmaReduce[mySum]
(−1 + 2n) −2+2n

−2−2A+2n

(1 + 2A)(2 + 2A − n) 2A


−1+n A −1−A+n
Out[3]= +
n(1 + n) (1 + A)n(1 + n)

Specializing A to n − 1 gives
sol = sol/.{A → n − 1}//Together
In[4]:=

2(−1 + 2n) −2+2n

−1+n
Out[4]= sol =
n(1 + n)

With sharp eyes one can see already that this result can be transformed to the left-hand side
of (18). However, this can be done automatically with Sigma by telling it to use 2n


n
:
SigmaReduce[sol, n, Tower → {SigmaBinomial[2n, n]}]
In[5]:=

1 2n
Out[5]= sol =
n+1 n

Note that we not only proved the identity (18), but given the right-hand side, we discovered
the simplified left-hand side. This completes the proof of Conjecture B and yields
8
Note that the old recurrence defines uniquely the sequence tn . If sn is a solution of this recurrence, then
the sequence sn must agree with the sequence tn .
9
You can download the package from [Link]

37
Theorem 4.3. For n ∈ N,  
1 2n
tn = .
n+1 n
HW 25. Simplify
Pn
1. k=0 k k!;
Pn k m


2. k=0 (−1) k
;
Pn k m


3. k=0 (−1) k
Hk .
HW 26. Simplify
Pn 2
1. k=0 Hk ;
Pn 2
2. k=0 (Hm+k ) ;
Pn 3
3. k=0 Hk .

Last week we used the symbolic summation package Sigma to simplify a sum (and posed various
homeworks to simplify similar sums). In this regard, the following remark is relevant.
Remark 4.4. Simplifications of indefinite sums like
n
X
Hk = (n + 1)Hn − n
k=0

for n ∈ N often find simple verifications.

For instance, let L(n) be the left-hand side and R(n) be the right-hand side of the above
identity. Then the strategy is to show that both sides satisfy the same recurrence (telescoping
equation).
By definition we get for the left-hand side:

L(n + 1) − L(n) = Hn+1 for n ∈ N,

L(0) = 0.

We verify that also the right-hand side satisfies the same recurrence. Namely we get

R(n + 1) − R(n) = (n + 2)Hn+1 − (n + 1)Hn + n

1


= (n + 2) Hn + n+1 − (n + 1)Hn − 1
1
= Hn + 1 + −1
n+1
= Hn+1

for all n ∈ N and R(0) = (0 + 1)H0 − 0 = 0. Thus both sides satisfy the same recurrence with
the same initial value and thus both sides must agree:

L(n) = R(n) ∀n ∈ N.

38
We remark that the observation in the above remark is another important feature that can be
applied often in computer algebra calculations. Software packages like Sigma might be based
on rather complicated algorithms and non-trivial software, and thus one might doubt that the
result is correct. However, the verification can be carried out independently of the original code
either by hand (as above) or by much simpler code that we can trust.
HW 27. Verify the correctness of the first identity that you have derived in HW 26.

In the second part of this section we will emphasis that with further computer algebra tools
many of the hand-calculations of the last lecture can be skipped. Let us recall, what we
accomplished last week. We started to produce the first values of tn and obtained the table:
n 0 1 2 3 ... n ...
tn 1 1 2 5 . . . ? ...
Inspired by this enumeration
• we produced the general formula (14) which allows one to calculate any value for tn ;
• we looked at its generating function T (x) = ∞ n
P
n=0 tn x and obtained the closed form
1 1√
T (x) = − 1 − 4x (19)
2 2
with ∞ 1
√ X
1 − 4x = 2 (−1)n 4n xn ∈ Q[[x]];

n=0
n

• finally, we derived  
1 2n
tn = .
n+1 n
To establish these formulas we did hand calculations based on classical generating function
technologies. However, we used also modern computer algebra tools and verified correctness
with the package Sigma: namely, we proved Conjecture B (and thus Conjecture A).
In the second part of this section we will be even more extreme. Starting with the discovered
formula (14) we produce some more values, say
n 0 1 2 3 4 5 6
tn 1 1 2 5 14 42 132.
As it turns out, this data is completely sufficient to discover all the remaining ingredients! More
precisely, we load another package10 from the Algorithmic Combinatorics Group at RISC:
In[6]:= << RISC‘GeneratingFunctions‘

Package GeneratingFunctions version 0.8 written by Christian Mallinger Copyright Research

Institute for Symbolic Computation (RISC), Johannes Kepler University, Linz, Austria

Then given the first values of tn (i.e., for n = 0, 1, 2, 3, 4, 5) one can guess the linear recurrence
−2(1 + 2n)a(n) + (2 + n)a(1 + n) = 0 (20)
for tn as follows:
10
You can download the package GeneratingFunctions from [Link]
generatingfunctions/.

39
 In[7]:= treeRE = GuessRE[{1, 1, 2, 5, 14, 42}, a[n]]

Out[7]= {{−2(1 + 2n)a[n] + (2 + n)a[1 + n] == 0, a[0] == 1}, ”ogf”}

One might be scared that the guess of the recurrence is wrong. But one can use, e.g. the data
of t5 = 132 (which has not been used for the guessing) and verifies that the recurrence holds
not only for n = 0, 1, 2, 3, 4 but also for n = 5:

−2(1 + 2n)a(n) + (2 + n)a(1 + n) = −22a(5) + 7a(6) = 0.

This gives more confidence. Of course, one can repeat this game and test further values for
n = 7, 8, 9, 10 and get even more confidence. Still this is not a proof...
However, we can easily solve the discovered recurrence (20) with a(0) = 1 (see HW 28) and get
 
1 2n
an = .
n+1 n
HW 28. Given the sequence a(n) defined by

−2(2n + 1)a(n) + (n + 2)a(n + 1) = 0

1 2n


and a(0) = 1. Show that a(n) = n+1 n
holds.

Thus we get for free (modulo some clever computer algebra packages) the desired result, i.e.,
Conjecture 6. Finally, we can activate our summation tools and verify correctness (as we did
last week already).
SUMMARY: by simply pressing some buttons one can guess and afterwards verify the result
by means of computer algebra.

We conclude this section by observing that we can use again computer algebra to get also
the closed form (19). Namely, by using again the package GeneratingFunctions with the
command
In[8]:= treeDE = RE2DE[treeRE[[1]], a[n], t[x]]

Out[8]= {−1 − (−1 + 2x)t[x] − (−x + 4x2 )t′ [x] == 0, t[0] == 1}

P∞ n
we calculate a differential equation that is satisfied by the formal power series t(x) = n=0 tn x .
Formally this means that

0 = − 1 − (−1 + 2x)t(x) − (−x + 4x2 )Dx t(x)

∞
X X∞
n 2
= − 1 − (−1 + 2x) tn x + (−x + 4x ) tn nxn−1
n=0 n=1

holds.
Finally, we solve this differential equation with the Mathematica function DSolve and get the
desired closed form:
DSolve[treeDE, t[x], x]
In[9]:=

1 1√
Out[9]= {{t[x] → − 1 − 4x}}
2 2

40
Remark 4.5. Sometimes it is convenient to work not with inhomogeneous recurrences like
1
Hn+1 − Hn =
n+1
or equivalently
(n + 1)Hn+1 − (n + 1)Hn = 1
but with homogeneous versions (with possibly higher order). Namely, taking its shifted version

(n + 2)Hn+2 − (n + 2)Hn+1 = 1

and subtracting both versions gives

(n + 2)Hn+2 − (2n + 3)Hn+1 + (n + 1)Hn = 0. (21)

HW 29. Consider the QuickSort recurrence

(n + 1)Fn+1 − (n + 2)Fn = 2n, n≥0

and transform it to a homogeneous recurrence (of higher order).

Hint use the trick from above (shift and subtract) twice.

P∞
HW 30. Compute a differential equation for the generating function Q(x) = n=0 Fn xn where
Fn are the average comparisons to quicksort an array with n elements.
Hint: use, e.g., the homogeneous recurrence from the previous homework.

HW 31. Compute a differential equation for the generating function H(x) = ∞ n

P
n=0 Hn x (e.g.,
1
with RE2DE) and solve it (e.g., with DSolve). Compare your result with H(x) = − 1−x log(1−x)
derived in (13).

41
5 Formal power series: Part 2
5.1 Connection to analysis
In general, I promised that you will be dispensed from analysis. However, today the situation is
slightly different. The bad news is that we will connect our formal world to analysis, i.e., you will
see analysis arguments in this lecture :-( The good news is that this yields new constructions to
use cleverly computer algebra. The second good news is that this lecture will be an exception,
i.e., no analysis will appear from next week on. Summary: stay relaxed.
Let us start with the following simple observation: The formal power series world and the
analysis world (with power series) are different.
Example 5.1. Consider the formal power series ∞ n
P
n=0 n!x ∈ K[[x]]. If we restrict to K = R,
we come close to the analysis world. However, by the ratio test
(
(n + 1)!xn+1 ∞ x ̸= 0
lim n
= lim |(n + 1)x| =
n→∞ n!x n→∞ 0 x = 0,
the series converges only for x = 0. Thus as function the power series can be used only trivially.
(1+x)n
Example 5.2. The power series f (x) = ∞
P
n=0 n!
in analysis converges for all x ∈ R by the
ratio test:
(x + 1)n+1 n! x+1
lim = lim | | = 0.
n→∞ (n + 1)!xn n→∞ n
Thus we can define the non-trivial function
f : R → R, x 7→ f (x)
which is the exponential function:
f (x) = exp(1 + x) = ex+1 = e ex .
However the series is not an element in the formal power series ring R[[x]].
BUT: numerous series live in BOTH worlds!

Lecture from May 7, 2024

Example 5.3. In analysis we have
1
y ′ (x) =
1+x
for all x ∈] − 1, ∞[ for the function y :] − 1, ∞[→ R with y(x) = log(1 + x).
Does this relation carry over to K[[x]]? The answer is YES. Namely, for the formal power series
∞
X (−1)n−1
log(1 + x) = xn ∈ K[[x]],
n=1
n
∞
1 X
= (−1)n xn ∈ K[[x]]
1+x n=0

42
and the derivative Dx given in Definition 3.26 we have
∞ ∞
X (−1)n+1 n
X (−1)n+1
Dx log(1 + x) = Dx x = nxn−1
n=1
n n=1
n
∞ ∞
X X 1
= (−1)n+1 xn−1 = (−1)n xn = .
n=1 n=0
1+x

The following observation is crucial: For x ∈ C with |x| < 1 (in particularly for x ∈ R)
1
the functions log(1 + x) and x+1 (in the analysis world) have power series (Taylor series)
representations:
∞
X (−1)n−1
log(1 + x) = xn ,
n=1
n
∞
1 X
= (−1)n xn .
1+x n=0

Thus the formal power series world and the power series world from analysis match here.
Furthermore, our formal definition of the differentiation Dx in K[[x]] is the same as in the
analysis world.
More precisely, the following property holds.
P∞ n
Theorem 5.4. Let f (x) = n=0 fn x be a power series (an ∈ R) with convergency radius
r > 0, i.e., f (x) ∈ R for all |x| < r. Then f (x) is arbitrarily differentiable In particular, for
k ∈ N∗ we have
X∞
f (k) (x) = fn n(n − 1)(n − 2) . . . (n − k + 1)xn−k
n=k

for all x ∈ R with |x| < r.

Remark: the above statement holds also for complex power series (an ∈ C) where |x| < r means
that x ∈ C is inside the circle with radius r centered around 0.
An important consequence of Theorem 5.4 is the following property: for all n ∈ N and x ∈ C
with |x| < r we have

[xn ]f (k) (x) = [x0 ]Dk f (x) = f (k) (0)

= fk k(k − 1)(k − 2) . . . (k − k + 1)x0 = fk k!.

Hence
f (k) (0) [x0 ]Dk f (x)
fk = =
k! k!
for k ∈ N which is nothing else than Taylor’s formula in the analysis world. Note that we have
obtained this formula already earlier in Theorem 3.28 in the formal power series world.

(************************************************************************)
(* WARING: hardcore for complex analysis fans *)
(*...

43
Let D = {x ∈ C | |x| < r} for some 0 < r ∈ R and suppose that f : D → C is complex
differentiable at all points x ∈ D. Then f is infinitely many times (complex) differentiable in
D and ∞
X
f (x) = fn xn ∀x ∈ D
n=0

with
f (n) (0)
fn = . (22)
n!
*************************************************************************)

All what one should remember is that many functions are complex differentiable and thus have
a power series representation. In particular, there is a formula (see (22) which is again Taylor’s
formula) that can be used (in particular in computer algebra systems).
Example 5.5. The function f (x) = e−x is complex differentiable for D = C. Thus one can
compute the coefficients of its power series by (22):

f (n) (0) (e−x )(n) |x=0 (−1)n e0 (−1)n

fn = = = =
n! n! n! n!
and gets
∞ ∞
−x
X
n
X (−1)n
e = fn x = xn (23)
n=0 n=0
n!
for each x ∈ C.

We can use this observation to activate again computer algebra (and ignore all the analysis
(n)
calculations). Namely, instead of using analysis arguments (compute a formula for f n!(0) using
the known differentiation rules), we can rely again on our Mathematica tools from above.
Executing
In[10]:= fSeries = Series[e−x , {x, 0, 10}]
x2 x3 x4 x5 x6 x7 x8 x9 x10
+ O x11


Out[10]= 1−x+ − + − + − + − +
2 6 24 120 720 5040 40320 362880 3628800

we compute the coefficients of the power series expansion of e−x up to the coefficient of x10 .
Let us rewrite this representation in list form
In[11]:= fL = CoefficientList[fSeries, x]
1 1 1 1 1 1 1 1 1
Out[11]= {1, −1, ,− , ,− , ,− , ,− , }
2 6 24 120 720 5040 40320 362880 3628800

In other words, we used Mathematica to compute the list (f0 , f1 , . . . , f10 ). Then using the
package
In[12]:= << RISC‘GeneratingFunctions‘

Package GeneratingFunctions version 0.8 written by Christian Mallinger Copyright Research

Institute for Symbolic Computation (RISC), Johannes Kepler University, Linz, Austria

we can guess a recurrence of the coefficients fn by

In[13]:= rec = GuessRE[fL, f [n]]

44
Out[13]= {{f[n] + (1 + n)f[1 + n] == 0, f[0] == 1}, ogf}

Finally, we solve the recurrence with

In[14]:= RSolve[rec[[1]], f [n], n]
 (−1)n
Out[14]= f[n] →
Pochhammer[2, n − 1]

Remark 5.6. Let R be a commutative ring with 1, x ∈ R and n ∈ N. The Pochhammer

symbol is defined by
(x)n := xn̄ .
In Mathematica it is denoted by Pochhammer[x,n].
With
(−1)n (−1)n
= fn =
(2)n−1 n!
we have rediscovered (23) by utilizing our computer algebra toolbox.

1+2x
HW 32. For the function f (x) = 1−2x
there exists a complex series expansion. Find it.

1+x 2


HW 33. For the function f (x) = 1−x
there exists a complex series expansion. Find it.
q
1+x
HW 34. For the function f (x) = 1−x
there exists a complex series expansion. Find it.

HW 35. For the function f (x) = log( 1+x

1−x
) there exists a complex series expansion. Find it.

BP 6. For the above functions f (x) and complex series expansions find (the maximal) r > 0
such that ∞
X
f (x) = fn xn |x| < r.
n=0

We are now ready to state the following crucial connection between the formal and analysis
world.
Theorem 5.7. [Transfer principle] Let a(x) and b(x) be complex functions such that
a(x) = b(x)
for all |x| < r for some r > 0. Suppose that a(x) and b(x) have power series representations
such that for all |x| < r we have
∞
X
a(x) = an x n , an ∈ C.
n=0
∞ (24)
X
b(x) = bn x n , bn ∈ C.
n=0

Then
an = b n ∀n ∈ N.

45
In other words, if we are given two formal power series a(x), b(x) ∈ C[[x]] with (24) and we are
suspicious that they agree in the ring of formal power series C[[x]], i.e.,

a(x) = (a0 , a1 , a2 , . . . ) = (b0 , b1 , b2 , . . . ) = b(x), (25)

then we can either try to prove this identity formally in C[[x]] or we can use analysis! Namely, if
a(x) and b(x) can be evaluated for each |x| < r for some r > 0 and the corresponding functions
equal for all |x| < r (e.g., by looking up some formulas in an analysis text book), then it follows
automatically that also (25) holds.
In the following example we utilize the following well known result from analysis.
P∞ n
P∞ n
Lemma 5.8. If f (x) = n=0 fn x and g(x) = n=0 gn x are power series with radius of
convergence rf > 0 and rg > 0, respectively. Then
∞
X
f (x) + g(x) = (fn + gn )xn ,
n=0
∞
X n
X
n
f (x)g(x) = x fk gn−k
n=0 k=0

holds for |x| < min(rf , rg ).

e−x
HW 36. Verify that the real function A : ]−1, 1[ → R with x 7→ 1−x
satisfies
x
A′ (x) = A(x), A(0) = 1.
1−x
Note: By the same rules it follows that A (as complex function with inputs inside of the unit
circle) satisfies this differential equation.

Example 5.9. Let D = {x ∈ C | |x| < 1} be the points inside of the unit circle and consider
the complex function A : D → C with

e−x
A(x) = .
1−x
By HW 36 it follows that A(x) satisfies the differential equation
x
A′ (x) = A(x)
1−x
with A(0) = 1.
As a consequence, we can carry over this result to the formal power series world as follows.

• A(x) has a power series representation. Namely,

– e−x has a power series representation for x ∈ C, see (23).

1
= ∞ n
P
– 1−x n=0 x has a power series representation for all x ∈ D.

46
 – Thus by Lemma 5.8 A(x) has a power series representation. Namely,
∞ ∞ n
X (−1)n n
 X
n
 X
n
X (−1)k
A(x) = x x = x
n=0
n! n=0 n=0 k=0
k!

holds for all x ∈ D.

• a(x) = A′ (x) has a power series representation by Theorem 5.4.

More precisely, we have
X∞
A′ (x) = an x n
n=0

with
n+1
X (−1)k
an = (n + 1) .
k=0
k!

• b(x) = 1−x
x
A(x) has a power series representation by Lemma 5.8. More precisely, with
1
f (x) = A(x) and g(x) = 1−x we have

∞ n X k ∞
x X
n
X (−1)i X
A(x) = x x · |{z}
1 = bn x n
1−x n=0 k=0 i=0
i! n=0
| {z } gn−k
fk

with
k
n−1 X
X (−1)i
bn =
k=0 i=0
i!
for all x ∈ D.

Consequently by the Transfer Principle (Theorem 5.7) it follows that

an = b n ∀n ∈ N.

In particular it follows that

x
Dx A(x) = A(x) (26)
1−x
x
holds in the formal power series ring C[[x]] with the formal power series A(x), 1−x ∈ C[[x]]. As
a byproduct we get from an = bn the non-trivial identity
n+1 n−1 X
k
X (−1)k X (−1)i
(n + 1) = . (27)
k=0
k! k=0 i=0
i!

BP 7. Prove the identity (27) for all n ∈ N without analysis arguments (e.g., with symbolic
summation). In this way you will verify (26) purely formally (i.e., without using the transfer
principle from analysis).

47
5.2 Quotients of formal power series
As we have learned earlier (see Theorem 3.11) the ring of formal power series (K[[x]], +, ·)
with the Cauchy product · forms an integral domain. Thus we can follow the construction of
Recall 2.5 and obtain the field of quotients of K[[x]].
In various instances such a construction is non-trivial. E.g., the field of quotients of the polyno-
mial ring K[x] yields the rational function field K(x) and typical elements are x2x+1
+x+1
. However,
in our particular situation of formal power series the situation is surprisingly simple: Due to
Theorem 3.29 most of the elements in K[[x]] are already invertible. In particular, those elements
which are not invertible can be easily turned to invertible elements.
More precisely, consider two formal power series
∞
X
a(x) = an xn ∈ K[[x]] \ {0},
n=0
∞
X
b(x) = bn xn ∈ K[[x]] \ {0}.
n=0

Then there are integers α, β ∈ N and A(x), B(x) ∈ K[[x]] with

a(x) = xα A(x) where A(0) ̸= 0,
(28)
b(x) = xβ B(x) where B(0) ̸= 0.

Example 5.10. For b(x) = x3 − x4 = x3 (1 − x) ∈ K[[x]] we can choose β = 3 and B(x) = 1 − x

and get b(x) = xβ B(x) with with B(0) = 1 ̸= 0

Given such (28) we can form the quotient construction (compare Recall 2.5) and get
a(x) xα A(x)
= β . (29)
b(x) x B(x)
Note that B(0) ̸= 0 and thus B(x) has the invertible element B(x)−1 ∈ K[[x]] by Theorem 3.11.
Consequently,
a(x) xα A(x)
= β = xα−β A(x) · B(x)−1 .
b(x) x B(x) | {z }
∈K[[x]]

If α ≥ β we get xα−β ∈ K[x] ⊆ K[[x]] and thus the quotient in (29) is an element in K[[x]]. The
only “critical” situation is α < β.
Example 5.11. Take a(x) = 1 and b(x) = x3 − x4 . Then b(x) = x3 B(x) with B(x) = 1 − x.
Since B(0) ̸= 0 we can invert B(x) in K[[x]] and get
1
B(x)−1 = = 1 + x + x2 + x3 + . . . .
1−x
Thus we have
a(x) 1
= 3 = x−3 B(x)−1
b(x) x B(x)
= x−3 (1 + x + x2 + x3 + . . . ) = x−3 + x−2 + x−1 + x0 + . . .

48
This motivates us to define the following set.
Definition 5.12 (formal Laurent series).

K((x)) := {(an )n∈Z | an ∈ K and an ̸= 0 for only finitely many negative indices};

here we denote the two-sided zero sequence as usual by 0 = (. . . , 0, 0, 0, . . . ) ∈ K((x)).

Furthermore, we define the order of a = (an )n∈Z ∈ K((x)) \ {0} by

ord(a) = min{n ∈ Z | an ̸= 0} ∈ Z;

for the special case a = 0 we define ord(0) = ∞. In particular, for a ̸= 0 we use the notation
∞
X
a = a(x) = an x n .
n=ord(a)

Example 5.13. We have

1 1 1
= 3 = x−3 (1 + x + x2 + . . . )
x3 +x 4 x 1−x
X ∞
−3 −2 −1 0
= x + x + x + x + ··· = xn ∈ K((x)).
n=−3

Remark 5.14. Consider

R = {(an )n∈Z ∈ K((x)) | an = 0 for all n < 0} ⊆ K((x)).

Then R is isomorphic to KN . More precisely, we can identify a = (. . . , 0, 0, a0 , a1 , a2 , . . . ) with

(a0 , a1 , a2 , . . . ). In this way we can say that KN (which is equal to R) is contained in K((x)).

The operations + and · (Cauchy product) of K[[x]] naturally extend to K((x)) and yield a
commutative ring (K((x)), +, ·) where each element (except the 0 element) is multiplicative
invertible. Thus we get the following theorem.
Theorem 5.15. (K((x)), +, ·) is a field which contains (K[[x]], +, ·) as subring.

Proof. HW 37 (Basically everything is said above, just repeat the construction once more
carefully...)

Remark: The quotient field (K((x)), +, ·) of (K[[x]], +, ·) is also called the field or Laurent
series.
Remark 5.16. If one wants to implement the set K((x)), one has to encode the elements
a ∈ K((x)) \ {0}. Note that for d = ord(a) ∈ Z we have
∞
X
a= an xn = ad xd + ad+1 xd+1 + ad+2 xd+2 + · · · = xd (ad + ad+1 x + ad+2 x2 + . . . )
n=d

with ad ̸= 0. This yields the following natural data structure (implementation of K((x))): we
take the tuple (d, f ) with d ∈ Z and f ∈ KN where f = (ad , ad+1 , ad+2 , . . . ) ∈ KN with ad ̸= 0.

49
Of course, the infinite list f cannot be stored physically. But, depending on the application,
sufficiently many entries of f can be stored, e.g., in a linked list.
This convention is also useful if one simply wants to store an element a(x) from K[[x]] (and
not from K((x))): as above one can write a(x) = xd A(x) with A(0) ̸= 0 where d = ord(a) ∈ N.
I.e., one drops the first d − 1 zero elements of a at the beginning and starts to memorize the
list A where the first entry is non-zero . In addition to A one needs d ∈ N as offset to recover
the full representation of a(x) = xd A(x) ∈ K[[x]].

Lecture from May 14, 2024

5.3 Convergence in K[[x]] and K((x))
I promised that we will avoid analysis aspects in this lecture (except in Subsection 5.1). Even so
we will use the word “convergence” below, it has nothing to do with the analysis interpretation:
it is totally formally defined and can be considered as a new formal operation (like +, the Cauchy
product ·, Dx , inversion, etc.) in the setting of formal power series.
In the following we restrict to K[[x]], the extension to K((x)) is immediate.
Definition 5.17. Consider a sequence in K[[x]] (i.e., a sequence of formal power series11 ):
(ak (x))k≥0 with ak (x) ∈ K[[x]].
Then we say that (ak (x))k≥0 converges to a formal power series f (x) = ∞ n
P
n=0 fn x ∈ K[[x]] if
the following holds:
For all n ∈ N there exists a starting point l(= l(n)) ∈ N such that
fn = [xn ]al (x)
= [xn ]al+1 (x)
= [xn ]al+2 (x)
= a.s.o.
In other words: from a certain point on, namely l, the nth coefficient in the sequence (ak (x))k≥0
does not change and equals the corresponding coefficient fn of f (x).
We say that (ak (x))k≥0 is convergent if there exists a formal power series f (x) ∈ K[[x]] such
that (ak (x))k≥0 converges to f (x).

Note: if (ak (x))k≥0 converges to f1 (x) ∈ K[[x]] and f2 (x) ∈ K[[x]] then f1 (x) = f2 (x). This
uniqueness property enables us to introduce the following notation/definition/operation.
Definition 5.18. Let (ak (x))k≥0 be convergent. Then the uniquely determined f (x) ∈ K[[x]] to
which (ak (x))k≥0 converges is denoted by
lim ak (x) := f (x).
k→∞

As mentioned already above, we have introduced a new “fancy” operation limk→∞ ak (x) for a
sequence (ak (x))k≥0 in K[[x]] which is convergent (i.e., the n coefficient stabilizes within the
series/list of formal power series (a0 (x), a1 (x), a2 (x), . . . )).
11
More precisely, a sequence of sequences.

50
 1−xk
Example 5.19. Consider the formal power series ak (x) := 1−x
∈ K[[x]] with k ∈ N. Note
that we get

ak =(1 − xk )(1 + x + x2 + x3 + . . . )
=(1 + x + x2 + x3 + . . . ) − (xk + xk+1 + xk+2 + xk+3 + . . . )
=1 + x + x2 + · · · + xk−1 ∈ K[x].

In other words (in sequence notation KN ) we have


(ak (x))k≥0 = (0, 0, 0, 0, 0, . . . ),
(1, 0, 0, 0, 0, . . . )
(1, 1, 0, 0, 0, . . . )
(1, 1, 1, 0, 0, . . . )

(1, 1, 1, 1, 0, . . . ), . . .

Based on this pattern we conjecture that (ak (x))k≥0 is convergent with

∞
X 1
lim ak (x) = (1, 1, 1, 1, . . . ) = f n xn = with fn = 1.
k→∞
n=0
1−x

Let us prove this observation. Let n ∈ N be arbitrary but fixed. Then for l = n + 1 we get

fn = 1 = [xn ]al (x) = [xn ] an+1 (x)

| {z }
1+x+···+xn

= [xn ] an+2 (x)

| {z }
1+x+···+xn+1
n
= [x ] an+3 (x)
| {z }
1+x+···+xn+2

= a.s.o.

□
1
In other words, we can define the formal power series 1−x
by the limit of (ak (x))k≥0 .

This example generalizes to

P∞
Theorem 5.20. Let f (x) = n=0 fn xn ∈ K[[x]]. Then

f (x) = lim (f0 + f1 x + · · · + fn xn ).

n→∞ | {z }
∈K[[x]]

Proof. HW 38.

In particular, we get limit theorems (analogously to analysis) and thus can nicely calculate with
our new formal limit operation.

51
Theorem 5.21. If (ak (x))k≥0 and (bk (x))k≥0 are convergent, then (ak (x))k≥0 + (bk (x))k≥0 and
(ak (x))k≥0 · (bk (x))k≥0 are convergent. In particular, we have



lim (ak (x) + bk (x)) = lim ak (x) + lim bk (x) ,
k→∞ k→∞ k→∞



lim (ak (x) · bk (x)) = lim ak (x) · lim bk (x) .
k→∞ k→∞ k→∞

BP 8. Show the above theorem for the + operation.

The final operation in K[[x]], that we will consider in this lecture, is as follows: given two formal
power series, say
X∞
a(x) = an xn ∈ K[[x]]
n=0

and ∞
X
b(x) = bn xn ∈ K[[x]],
n=0

we want to carry out the composition

∞
X
(a ◦ b)(x) = a(b(x)) = an b(x)n .
n=0

The following questions arise: Under which assumptions can one define such an operation in
K[[x]] by using only finitely many field operations in K? Is a(b(x)) again a formal power series?
In order to justify and clarify these aspects, we will rely on our lim-construction from above.
Definition 5.22. Let (bn (x))n≥0 be a sequence of formal power series in K[[]x]] and define for
N ∈ N,
N
X
aN (x) := bn (x) ∈ K[[x]].
n=0

If the newly defined sequence ((aN (x))N ≥0 of formal power series in K[[x]] is convergent, i.e.,
there is a formal power series b(x) ∈ K[[x]] with

lim aN (x) = b(x),

N →∞

we define
∞
X  N
X 
bn (x) := b(x) = lim an (x) .
N →∞
n=0 n=0

In this case, show that

HW 39.
∞
X N
X
k k
[x ]b(x) = [x ]bn (x)(= lim [xk ]bn (x));
N →∞
n=0 n=0

and

52
HW 40.
∞
X  N
X 
Dx b(x) = Dx bn (x) = lim Dx bn (x) .
N →∞
n=0 n=0

(1+x)n
HW 41. Show that for the sequence (bn (x))n≥0 with bn (x) = n!
∈ K[[x]] the limit
P∞ PN

n=0 bn (x) = limN →∞ n=0 bn (x) does not exist.

A slight generalization of the last homework yields the following criterion when such a limit
construction exists.

Theorem 5.23. Let (bn (x))n≥0 be a sequence of formal power series in K[[x]]. Then the
following statements are equivalent:
PN

1. n=0 bn (x) N ≥0 is convergent, i.e., there exists a b(x) ∈ K[[x]] with

∞
X
bn (x) = b(x);
n=0

2. limn→∞ bn (x) = 0;

3. limn→∞ ord(bn (x)) = ∞.

In other words, we can build an infinite sum of power series, if the order of the summands
get larger and larger. This property will be crucial to define the composition in the next
section. However, we will give a direct argument below – so do not worry if you are lost with
Theorem 5.23...

5.4 Composition in K[[x]] (resp. K((x)))

We are now ready to define the composition of
∞
X
a(x) = an xn ∈ K[[x]]
n=0

and ∞
X
b(x) = bn xn ∈ K[[x]]
n=0

by using the construction from above.

The only extra requirement is that
b(0) = 0,
or equivalently, b0 = 0 holds. With this property we can pullout x and can write

b(x) = x b̃(x)

53
for some b̃(x) ∈ K[[x]]. Now define

bn (x) := an b(x)n = an xn b̃(x)n ∈ K[[x]].

Then one can easily see that ord(bn (x)) ≥ n and thus

lim ord(bn (x)) = ∞.

n→∞

Consequently, we can apply Theorem 5.23 and it follows that there is a formal power series
b(x) ∈ K[[x]] with
∞
X ∞
X
b(x) = bn (x) = an b(x)n = a(b(x)) = (a ◦ b)(x).
n=0 n=0

Note that this construction enables one to compute explicitly the coefficients of b(x). More
precisely, with the following arguments we can neglect Theorem 5.23 and can justify our above
construction directly:
∞
X ∞
X
m n m
[x ] an b(x) =[x ] an xn b̃(x)n
n=0 n=0
m
=[x ]a0 x0 b̃(x)0
+ [xm ]a1 x1 b̃(x)1
(30)
..
.
+ [xm ]am xm b̃(x)m
+ [xm ]am+1 xm+1 b̃(x)m+1 + [xm ]am+2 xm+2 b̃(x)m+2 + |{z}
...
| {z } | {z }
0 0 0

In other words, only the first m + 1 summands have to be considered in order to get the mth
coefficient. More precisely, for each of the m + 1 summands ai xi b̃(x)i with i = 0, . . . , m the
mth coefficient can be calculated by using only finitely many operations of the addition and
the Cauchy product in K[[x]]. In particular, these latter operations, can be accomplished by
using only the first coefficients of a(x) and b(x) and a finite number of field operations in K.
The construction of the composition can be summarized in

Definition 5.24. Let a(x) = ∞ n

P
n=0 an x ∈ K[[x]] and b(x) ∈ K[[x]] with b(0) = 0. Then the
composition is defined by
∞
X
(a ◦ b)(x) = a(b(x)) = an b(x)n ∈ K[[x]].
n=0

1
Example 5.25. Let f (x) = 1−x
and g(x) = x2 . Since g(0) = 0, we can built the composition
∞ ∞
X
2 k
X 1
f (g(x)) = (x ) = x2k = .
k=0 k=0
1 − x2

54
 1 1
HW 42. Let f (x) = x−1
and g(x) = 1−x
− 1. Calculate the first 20 coefficients of f (g(x)).

Summarizing, we have introduced a new operation, namely composition a(b(x)) of a(x) and
b(x) that is always possible if b(0) = 0. Conversely, if b(0) ̸= 0 and a(x) is not a polynomial,
the above observation (30) does not work, i.e., cannot be defined: the calculation of the nth
coefficient cannot be carried out by using only a finite number of field operations in K.
Remark 5.26. In analysis more general operations are possible: if a series converges, one can
define an infinite sum whose summands are from R. In short, if certain series converge, more
general compositions might be possible with b(0) ̸= 0 and a(x) ∈
/ R[[x]] \ R[x]. This case has
been presented, e.g., in Example 5.2.

We conclude with another nice property which is connected to the inversion w.r.t. composition.
Example 5.27. Consider
∞
X 1 n
exp(x) = x ∈ K[[x]],
n=0
n!
∞
X (−1)n+1
log(1 + x) = xn ∈ K[[x]].
n=1
n

We observe the following:

• Since ord(log(1 + x)) = 1, we can carry out the composition: there is a formal power
series g(x) ∈ K[[x]] with
g(x) = exp(log(1 + x)).

• Using analysis we get

exp(log(1 + x)) = 1 + x
as functions.

Thus by the transfer principle (see Theorem 5.7) we conclude that

exp(log(1 + x)) = g(x) = 1 + x
holds also in K[[x]]. Now define
b(x) := exp(x) − 1 ∈ K[[x]],
B(x) = log(1 + x) ∈ K[[x]]
with ord(b(x)) = 1 = ord(B(x)). Then by exp(log(1 + x)) = 1 + x we conclude that
b(B(x)) = x.
Analogously we can conclude that
x = B(b(x)) = log(exp(x))
holds.

55
More generally, we have the following theorem.

Theorem 5.28. Let b(x) ∈ K[[x]] with12 ord(b(x)) = 1. Then there is a unique B(x) ∈ K[[x]]
with ord(B(x)) = 1 such that
B(b(x)) = x = b(B(x)).

Remark 5.29. The above theorem is constructive: the corresponding B can be computed with
the Lagrange inversion formula; further details are skipped.

Example 5.30. Consider the formal power series

∞  
1 1√ 1 1 X 21
T (x) = − 1 − 4x = − (−1)n 4n xn ∈ K[[]x]]
2 2 2 2 n=0 n

with ord(T (x)) = 1. By Theorem 5.28 we conclude that there is a unique S(x) ∈ K[[x]] with
ord(S(x)) = 1 and
S(T (x)) = T (S(x)) = x.

HW 43. Find S(x) ∈ K[[x]]. (Hint use the property T (x)2 − T (x) + x = 0.)

Let us summarize the operations in K[[x]] that have been introduced in this lecture:

1. component-wise addition + (see Definition 3.2);

2. scalar multiplication ∗ (see Definition 3.2);

3. Hadamard products ◦ (see Definition 3.7);

4. Cauchy products · (see Definition 3.7);

5. coefficient functional [xn ] (see Definition 3.16);

R
6. differentiation/integration Dx , x (see Lemma 3.24 and Definition 3.26);

7. multiplicative inverse (see Theorem 3.29);

8. limit construction (see Definition 5.18);

9. composition (see Definition 5.24).

10. inversion of composition (see Theorem 5.28).

12
Note that b(0) = 0 holds.

56
Lecture from May 28, 2024

6 c-finite sequences
Later we will consider recurrences where the coefficients may depend on n (see, e.g., (2)
and (21)). But in this section we will restrict to recurrences which are homogeneous and
where the coefficients do not depend on the shift-variable.

Definition 6.1. We call a sequence (an )n≥0 ∈ KN c-finite of order r if there exists a linear
recurrence of order r with constant coefficients that has (an )n≥0 as solution. This means that
there are c0 , . . . , cr ∈ K with cr ̸= 0 such that

cr an+r + cr−1 an+r−1 + · · · + c0 an = 0 (n ∈ N).

We call such a recurrence with constant coefficients also c-finite recurrence.

The Fibonacci numbers Fn with n ≥ 0 are one of the most prominent examples of c-finite
sequences. They appear in Leonardo di Pisa’s work (∼ 1200) and can be defined by the
following c-finite recurrence relation:

Fn+2 = Fn+1 + Fn (n ≥ 0)
F0 = 0 (31)
F1 = 1.

Together with the initial values we get the following first values
n 0 1 2 3 4 5 6 7 8 ...
Fn 0 1 1 2 3 5 8 13 21 . . .

Fn counts, e.g., the number of rabbit couples under the following assumptions: a fresh born
couple needs 2 month to generate its first couple. From that month on it regularly produces a
new couple each month. In this model we suppose in addition that all the born couples behave
the same and never die. Then the tree of growth looks as follows:

month
1 1
2 1

3 1 2
4 1 3 2
5 1 4 3 2 5

6 1 6 4 3 7 2 8 5

57
Example 6.2. Given Fn by its defining recurrence relation and initial values (31), we can
derive its generating function as follows:
∞
X
F (x) = Fn xn
n=0
∞
X
= F0 + F1 x + Fn+2 xn+2
n=0
∞
X
=x+ (Fn + Fn+1 ) xn+2
n=2
∞
X ∞
X
n+2
=x+ Fn x + Fn+1 xn+2
n=0 n=0
∞
X X∞
= x + x2 F n xn + x Fn+1 xn+1
n=0 n=1
2
= x + x F (x) + xF (x)
and thus
(1 − x − x2 )F (x) = x
or equivalently
x
F (x) = . (32)
1 − x − x2
This means that F (x) equals the inverse element of 1 − x − x2 times x. In short, the closed
form of F (x) is a rational function in K(x).
More generally, we obtain the following result.
Theorem 6.3. Let (an )n≥0 be a sequence in K.

(an )n≥0 satisfies a c-finite recurrence

an+r + cr−1 an+r−1 + · · · + c0 an = 0, n∈N

|{z}
̸=0

with c0 , . . . , cr−1 ∈ K
⇕
∞
X p(x)
an x n =
n=0
1 + cr−1 x + · · · + c0 xr
for some p(x) ∈ K[x] with deg(p(x)) < r.

Proof. HW 44. Hint: for ⇓ see the above example; for ⇑ do coefficient comparison in
∞
r

X
1 + cr−1 x + · · · + c0 x an xn = p(x).
n=0

58
Note that the above theorem is constructive if the field operations in K can be computed.
Namely, suppose that (an )n≥ ∈ KN is given by a c-finite recurrence of order r

an+r + cr−1 an+r−1 + · · · + c0 an = 0 (33)

|{z}
̸=0

for some c0 , . . . , cr−1 ∈ K and initial values a0 , . . . , ar−1 ∈ K. Then one can compute p(x) ∈ K[x]
with deg(p(x)) < r such that
∞
X p(x)
an x n = .
n=0
1 + cr−1 x + · · · + c0 xr

Conversely, suppose that we are a given formal power series ∞ n

P
n=0 an x whose closed form is
a rational function 1+cr−1p(x)
x+···+c0 xr
for some p(x) ∈ K[x] with deg(p) < r. Then the sequence
(an )≥0 satisfies the c-finite recurrence (33).

Example 6.4 (cont. Ex, 6.2). Consider the Fibonacci numbers with the defining equation (31).
Then by Theorem 6.3 we know that
∞
X p(x)
F n xn =
n=0
1 − x − x2

with p(x) = α x + β where α, β ∈ K. Equivalently we have

∞
X
2
(1 − x − x ) Fn xn = p(x). (34)
n=0

By looking at the constant term on both sides we conclude

1 · F0 = p(0) = β

and thus β = 0. In order to get a constraint for α we apply Dx to (34) (i.e., shift the sequence
to the left) and take again the costant term. Then we get:
∞
X ∞
X
0 n 2
LHS = [x ](−1 − 2x) Fn x + (1 − x − x ) nFn xn−1 = −F0 + F1 = 1,
n=0 n=1
0 ′
RHS = [x ]p (x) = α.

Thus α = 1 and we get p(x) = x. In other words, we have rediscovered (rederived) the
identity (35).

6.1 Solving c-finite recurrences

On page 13 you have seen how one can solve an arbitrary first-order recurrence using the
“variation of constant” method. In the following we will restrict to c-finite recurrences but
generalize to the situation that the recurrences may have any order.

59
More precisely, we will present two different (but related) tactics how one can compute a closed
form solution of a given c-finite recurrence of order r. For simplicity, we consider again our
Fibonacci sequence (Fn )n≥0 defined by (31).
Approach 1: usage of the rational function representation.
Using Theorem 6.3 (or our explicit calculation in Example 6.2) we have
∞
X x
F (x) = F n xn = . (35)
n=0
1 − x − x2

Exploiting this special closed form we can derive the solution of the recurrence

Fn+2 − Fn+1 − Fn = 0

together with its initial values F0 = 0 and F1 = 1 in closed form.

More precisely, let us factorize the denominator 1 − x − x2 in (35) in the form

1 − x − x2 = (1 − r+ x)(1 − r− x);

here we can use any computer algebra system and get

√ √
1+ 5 1− 5
r+ = , r− = .
2 2

Hence by partial fraction decomposition (PFD) we can write

A B
F (x) = +
1 − r+ x 1 − r− x
for constants A, B, free x.

Lecture from June 4, 2024

How can one determine A, B, i.e., how can one carry out the partial fraction decomposition?
Here we indicate three possibilities:

1. Use your favorite computer algebra system. E.g., in Mathematica use the command
Apart[F,x].
2. One can activate the Extended Euclidean algorithm. More precisely, let p(x), q(x) ∈ K[x]
with gcd(p, q) = 1. Then there are α(x), β(x) ∈ K[x] such that

α(x)p(x) + β(x)q(x) = 1(= gcd(p(x), q(x)))

⇕
α(x) β(x) 1
+ = .
q(x) p(x) p(x)q(x)
Thus one can read off A and B (using some further polynomial divisions).

60
 3. Often also the traditional method is fast. Looking at the ansatz
A B
F (x) = +
1 − r+ x 1 − r− x
we get

A = (1 − r+ x)F (x) x7→ r1

+

(1 − r+ x)x
=
(1 − r+ x)(1 − r− x) x7→ r1
+
x
=
1 − r− x x7→ r1+
1/r+ 1 1
= = =√
1 − r− /r+ r+ − r− 5

and
1 1
B = (1 − r− x)F (x) x7→ r1
= ... = = −√ .
− r− − r+ 5

Thus
1 1 1 1
F (x) = √ −√
5 1 − r+ x 5 1 − r− x
∞ ∞
1 X n n 1 X n n
=√ r+ x − √ r− x
5 n=0 5 n=0
∞
X 1  n n

= √ r+ − r− xn
n=0
5

which gives the Euler–Binet formula (1843): for all n ∈ N,

1  n n

Fn = √ r+ − r− .
5

Approach 2: finding all solutions via roots.

We make the ansatz
Fn = αn
for an indeterminate α ∈ C∗ . Thus

0 =Fn+2 − Fn+1 − Fn (36)

=αn+2 − αn+1 − αn
αn (α2 − α − 1)
= |{z}
̸=0

61
and consequently α is a root of the polynomial

p(x) = x2 − x − 1 = (x − r+ )(x − r− ). (37)

n n
Hence r+ and r− are solutions of (36). In particular, by HW 45a,
n n
Gn = A r+ + Br−

with A, B ∈ C is a solution of (36).

Note:
n n
V := {A (r+ )n≥0 + B(r− )n≥0 | A, B ∈ C}
is a vector space over C. In particular, by HW 45b,
n n
(r+ )n≥0 , (r− )n≥0

is a basis of V . Moreover, by HW 46 it follows that V contains all solutions of (36), i.e.,

V = {(an ) ∈ Cn | an+2 − an+1 − an = 0 for all n ≥ 0}.

HW 45. Let r+ and r− ∈ C be the roots of q(x) = x2 − x − 1 ∈ C[x].

(a) Check that

A (r+ )n + B (r− )n
with A, B ∈ C are solutions of the c-finite recurrence an+2 − an+1 − an = 0.
(b) In particular, show that ((r+ )n )n≥0 and ((r− )n )n≥0 are linearly independent over C.
HW 46. Define

V = {(an )n≥0 ∈ KN | an+2 − an+1 − an = 0 ∀n ∈ N}.

Show that V = {A ((r+ )n )n≥0 + B ((r− )n )n≥0 | A, B ∈ C}.

In the above example we were lucky: the polynomial in (37) has two different roots and thus
yields two different solutions. What happens if the corresponding polynomial has roots with
higher multiplicity. Let us consider the most degenerated case: a polynomial which has only
one root (with non-trivial multiplicity).
Example 6.5. Consider the sequence (an )n≥0 defined be the c-finite recurrence

an+3 − 3an+2 + 3an+1 − an = 0 (38)

and the initial values a0 = 0, a1 = 1 and a2 = 3.

As above we make the ansatz
fn (x) = xn
with x ∈ C for a solution of (38). This gives

0 =fn+3 (x) − 3fn+2 (x) + 3fn+1 (x) − fn (x)

=xn (x3 − 3x2 + 3x − 1) = xn (x − |{z}
1 )3 (39)
=α

62
for all n ∈ N. Thus with x = α = 1 we get a solution (1n )n≥0 of (38).
Unfortunately, there is only 1 root (but with multiplicity 3). However, a recurrence of order 3
has 3 linearly independent solutions. Can we determine the missing two solutions whose linear
span provides all solutions?
The answer is yes by the following trick: We apply the differential operator Dx to (39) and
find
′ ′ ′
0 =fn+3 (x) − 3fn+2 (x) + 3fn+1 (x) − fn′ (x)
=nxn−1 (x − 1)3 + xn 3(x − 1)2 = (x − 1)2 q1 (x)
with q1 (x) = nxn−1 (x − 1) + 3xn = xn−1 (n(x − 1) − x). Thus
fn′ (x)|x7→1 = n · 1n−1 = n
is a solution of (38). Repeating the trick by applying Dx2 to (39) we obtain
′′ ′′ ′′
0 =fn+3 (x) − 3fn+2 (x) + 3fn+1 (x) − fn′′ (x)
=(x − 1)1 q2 (x)
for some polynomial expression q2 (x). Thus
fn′′ (x)|x7→1 = n(n − 1) · 1n−2 = n(n − 1)
is also a solution of (38). Note that applying this trick once more, i.e., applying Dx3 to (39)
does not yield any extra solution because on the right-hand side the factor (x − 1) disappears
(which turned the right-hand side to zero when one sets x to 1).
Summarizing, we find the set of solutions
L = {c1 (1)n≥0 + c2 (n)n≥0 + c2 (n(n − 1))n≥0 | c1 , c2 , c3 ∈ K}.
As it turns out the three solutions are linearly independent, i.e.,
c1 (1)n≥0 + c2 (n)n≥0 + c2 (n(n − 1))n≥0 = 0
if and only if c1 = c2 = c3 = 0. Since there can be at most three linearly independent solutions,
L contains all solutions and thus (an )n≥0 ∈ L. Consequently, there exist c1 , c2 , c3 ∈ K such that
an = c1 1 + c2 n + c3 n(n − 1) (n ∈ N).
In order to determine the ci we look at the special cases n = 0, 1, 2:
0 = c1
1 = c1 + c2
3 = c1 + 2c2 + 2c3 .
Solving this linear system yields the unique choice c1 = 0, c2 = 1 and c3 = 21 . Consequently
1 1
an = n + n(n − 1) = n(n + 1) (n ∈ N)
2 2
Note that we can verify this result also by the following argument: both sides are a solution
of the same recurrence of order 3 and both sides agree with the first three values n = 0, 1, 2.
Thus they must agree for all n.

63
Combining the ideas from the two examples above (take all roots α1 , . . . , αk of the corre-
sponding polynomial and extract further solutions by applying the differential operator Dxi for
i = 1, . . . , mi − 1 where mi is the multiplicity of the root αi ) produces all solutions of a given
c-finite recurrence. More precisely, we obtain the following general result.

Theorem 6.6. For c0 , . . . , cr−1 ∈ K with c0 ̸= 0 suppose that

p(x) = xr + cr−1 xr−1 + · · · + c1 x + c0 = (x − α1 )m1 (x − α2 )m2 . . . (x − αk )mm

is a complete factorization (i.e., mi ∈ N∗ with m1 + m2 + · · · + mk = r and the13 αi ∈ K are

pairwise different). Then the r sequences

(α1n )n≥0 (n α1n )n≥0 (n2 α1n )n≥0 ... (nm1 −1 α1n )n≥0
(α2n )n≥0 (n α2n )n≥0 (n2 α2n )n≥0 ... (nm1 −1 α2n )n≥0
..
.
(αkn )n≥0 (n αkn )n≥0 (n2 αkn )n≥0 ... (nmk −1 αkn )n≥0

form a basis of the K-vector space

{(an )n≥0 | an+r + cr−1 an+r−1 + · · · + c1 an+1 + c0 an = 0 for all n ≥ 0}.

BP 9. Prove Theorem 6.6 for the special case r = 2.

BP 10. Prove Theorem 6.6 for the special case r = 3.

Lecture from June 11, 2024

6.2 Application: AVL-trees
Recall the definition of a binary search tree from Section 1.4: It is a binary tree where in each
subtree with root x all the elements in its left subtree are smaller than x and all elements in
its right subtree are larger than x.
We refine this definition as follows: an AVL-tree is a binary search tree in which for each node
the heights of the two subtrees differ at most by 1.

Example 6.7. Consider the binary search tree

11

10 15
14 17
13
Note that p(x) must split into linear factors in K; if this is not possible one has to extend the field K.

64
which actually is an AVL-tree. However, after inserting 18 into this binary search tree we get

11
10 15

14 17
18
which is not an AVL-tree anymore: the right subtree of 11 has height 3 but the left subtree
has height 1. As it turns out, one can rotate such an almost-AVL-tree (an AVL-tree which got
spoiled by one extra insertion). More precisely, by choosing the first node to the right as new
root (in our case 15) and changing some pointers, one gets another binary search tree

15

11 17
10 14 18
which is again an AVL-tree.

In general, the following holds for an AVL-tree T with height h:

1. The insertion/deletion of an extra element in T yields a new binary search tree (which is
not necessarily an AVL tree). Here the worst case complexity is in O(h) (in worst case
one has to walk down the longest possible path which has length h).
2. In O(1) steps (by changing some pointers) one can rebalance the derived binary search
tree to an AVL-tree in case of an insertion; and in O(h) steps one can rebalance the tree
to an AVL-tree in case of a deletion; for further details we refer to the standard literature
that deals with algorithms and data structures.

Combining the two steps one obtains the following result: in worst case one can insert/delete
an element of an AVL-tree in O(h) steps and obtains again an AVL-tree. In particular, one can
search an element in an AVL-tree with at most O(h) operations.
In this lecture we will not explore further this rebalancing process for insertion and deletion.
But we will demonstrate the presented toolbox from above. Namely, we will show that the
worst case height of an AVL tree with n stored elements is O(log(n)). In other words we can
show that the search, the deletion and insertion of an element in an AVL-tree requires at most
O(log(n)) operations!
In order to obtain this result, we consider the worst situation: fix the height h and construct
the most stupid AVL-tree (in the sense of storing elements), i.e., a tree with as less nodes as
possible. More precisely, we will compute

M (h) = the minimal number of nodes in an AVL-tree with height h.

The only binary search tree of height 0 has exactly one element:

65
In particular, we have
M (0) = 1.
If one wants to construct an AVL-tree with height 1 with as less nodes as possible one ends up
at
• or •
• •
Thus
M (1) = 2.
If one wants to obtain an AVL-tree of height 2 with a minimal number of nodes, one finds the
following two shapes:
• or •

• • • •
• •
Consequently
M (2) = 4.
More generally, if one wants to obtain an AVL-tree with height h (h ≥ 2) with as less nodes as
possible, one needs one node for the root plus two subtrees where

• one must have height h − 1 (in order to get height h); here M (h − 1) are the minimal
number nodes to manage this.
• the other subtree should have only height h − 2 – otherwise we spent too many nodes;
here M (h − 2) is the minimal number of nodes.

In total, we get
M (h) = 1 + M (h − 1) + M (h − 2) (h ≥ 2)
M (0) = 1, (40)
M (1) = 2.
This is all we need to run our c-finite machinery! First, we compute a homogeneous version
(compare Remark 4.5) and get
M (h) −M (h − 1) −M (h − 2) =1
− M (h − 1) −M (h − 2) −M (h − 3) = 1
M (h) −2M (h − 1) +M (h − 3) = 0.
Now we activate Theorem 6.6 that is built into Mathematica:
In[15]:= RSolve[M[h] − 2M[h − 1] + M[h − 3] == 0, M[h], h]//FullSimplify
√  h √  h
     
 1 1
Out[15]= M[h] → c1 1− 5 + c2 1+ 5 + c3
2 2

This means that

√  h √  h
     
 1 1
c1 1− 5 + c2 1+ 5 + c3 | c1 , c2 , c3 ∈ C
2 2

66
provides the full solution space and thus there exist c1 , c2 , c3 ∈ C such that
√  h √  h
     
1 1
M (h) = c1 1− 5 + c2 1+ 5 + c3
2 2
holds for all h ∈ N. Finally, looking at h = 0, 1, 2 we get the linear system

1 = c1 + c2 + c3
1 √  1 √ 
2 = c1 1 − 5 + c2 1 + 5 + c3
2 2
2
√ √  2
    
1  1
4 = c1 1− 5 + c2 1+ 5 + c3 .
2 2

Solving it (using the Gauss algorithm) yields

1 √
c1 = (5 − 2 5),
5
1 √
c2 = (5 + 2 5),
5
c3 = −1.

Remark: Providing in addition the initial values to RSolve, this calculation can be carried out
in one stroke:
In[16]:= RSolve[M[h] − 2M[h − 1] + M[h − 3] == 0
&&M[0] == 1&&M[1] == 2&&M[2] == 4, M[h], h]//FullSimplify
!
√  1 √  h  √  1 √  h
   
1 
Out[16]= 5−2 5 1− 5 + 5+2 5 1+ 5 −5
5 2 2

More precisely, we get √ √

5−2 5 h 5+2 5 h
M (h) = −1 + r− + r+ . (41)
5 5
√
5+2 5 h
Since r− < 1 one can easily see that M (h) is asymptotically equal to 5
r+ , i.e.,
√
5+2 5 h
M (h) ∼ r+ .
5
Furthermore, √ √
5+2 5 h 5+2 5 h
r+ − 1 < M (h) < r+ + 1
5 5
if h is sufficiently large. Now take any AVL-tree with n nodes and let h be its maximal height.
Then
M (h) ≤ n.
HW 47. Show that that
h ≤ 1.44 log2 (n) + const.

This shows that the worst case to find/delete/insert and element is in O(log(n)).

67
6.3 Closure properties
The following powerful machinery allows one to prove beautiful identities in a jiffy.
Theorem 6.8. Let (an )n≥0 and (bn )n≥0 be c-finite sequences in K of order r and s, respectively.
Then the following holds.

1. (an + bn )n≥0 is c-finite of order ≤ r + s.

2. ( nk=0 ak bn−k )n≥0 is c-finite of order ≤ r + s.
P

In particular, we get the special case: ( nk=0 ak )n≥0 is c-finite of order ≤ r + 1.

P

3. (an · bn )n≥0 is c-finite of order ≤ r · s.

4. For any m ∈ N∗ and p ∈ {0, 1, . . . , m − 1}: (am·n+p )n≥0 is c-finite of order ≤ r.
5. For any m ∈ N∗ : (a⌊ mn ⌋ )n≥0 is c-finite of order ≤ m · r.

In particular, if the c-finite recurrences of (an )n≥0 and (bn )n≥0 of order r and s are given
explicitly and the field operations of K can be computed, the c-finite recurrences in statements
(1)–(5) can be computed.

The constructive versions of this theorem has been implemented, e.g., in Mallinger’s package
GeneratingFunctions.
Example 6.9. Prove
F2n = 2 Fn Fn+1 − Fn2 , n ∈ N. (42)
Proof strategy: derive a recurrence for
an := F2n − 2 Fn Fn+1 + Fn2 :
|{z} | {z } |{z}
rec of rec of rec of
order≤ 2 order≤ 4 order≤ 4
| {z }
rec of order≤ 4 + 4 = 8
| {z }
rec of order≤ 2 + 8 = 10

One option is to compute the recurrence of an explicitly (see the homework below). However,
for the proof of (42) or equivalently for the proof of
an = 0 ∀n ≥ 0 (43)
it suffices to bound the order of recurrence of an . We start with the well known Fibonacci
recurrence (36) which has order 2. Thus by part (3) of Theorem 6.8 it follows that 2 Fn Fn+1
and −Fn2 have c-finite recurrences of order ≤ 4. But then 2 Fn Fn+1 − Fn2 is c-finite of order ≤ 8
by part (1) of Theorem 6.8. Finally, by part (4) of Theorem 6.8 it follows that F2n is c-finite of
order ≤ 2 and thus with part (1) of Theorem 6.8 the final sequence an is c-finite of order ≤ 10.
Finally, we verify that the first 10 values of an are zero
a0 = a1 = a2 = · · · = a9 = 0
which proves (43) and thus (42).

68
Remark. Often students in the first year claim to have a proof of an identity by demonstrating
that it is correct for the first instances. In general, this is of course nonsense and the teacher
will show a tedious and lengthy proof. However in the c-finite world, this naive approach is
completely valid! Check the first instances in order to obtain a rigorous proof. Warning: we
are only allowed to do this by a strong theory that is hidden behind and which tells us how
many values we have to check. So one first has to do the work (and prove Theorem 6.8) but
afterwards one can prove identities as above in the simplest way (without cheating!).

HW 48. Use GeneratingFunctions.m (or another computer algebra package) to derive a

c-finite recurrence for (an )n≥0 with an = F2n − 2Fn Fn+1 + Fn2 .

3
HW 49. Prove F3n = Fn+1 3
+ Fn3 − Fn−1 for n ≥ 1.

P∞ x(1−2x−x2 )
HW 50. Prove n=0 Fn3 xn = (1−4x−x2 )(1+x−x2 )
.

HW 51. Use GeneratingFunctions.m (or another computer algebra package) to derive a c-

finite recurrence for Kepler’s identity14 : Fn+1 Fn−1 − Fn2 = (−1)n . Verify the correctness of the
identity.

Pn
HW 52. Find/prove k=0 Fk = Fn+2 − 1 for n ∈ N.

After exploiting this wonderful machinery, let us look behind the scene and prove it (at least
in parts).
Proof of Theorem 6.8. Let (an )n≥0 and (bn )n≥0 be c-finite sequences in K of order r and s,
respectively. With Theorem 6.3 we get
∞
X p(x)
an x n = , deg(p) < r,
n=0
1 + cr−1 x + · · · + c0 xr
|{z}
̸=0
∞
X q(x)
bn x n = , deg(q) < s
n=0
1 + ds−1 x + · · · + d0 xs
|{z}
̸=0

for some p(x), q(x) ∈ K[x].

(1) By Theorem 5.7 it follows that
∞ ∞ ˜
X
n
X p(x)
an x + bn x n =
n=0 n=0
(1 + cr−1 x + · · · + c0 xr )(1 + ds−1 x + · · · + d0 xs )
14
This identity is often named as Cassini’s identity. However, Peter Paule observed that this identity was
discovered much earlier by Johannes Kepler. Since this lectures takes place at the Johannes Kepler University
(JKU), it seems very appropriate to rename it accordingly and to give proper credits to Johannes Kepler.

69
with deg(p̃(x)) < r + s. Thus by Theorem 6.3 there exists a recurrence of (an + bn )n≥ of order15
≤ r + s.
(2) By the Cauchy product and Theorem 5.7 it follows that
∞ n ∞ ∞
X
n
X X
n
 X  p(x) q(x)
x ak bn−k = an x bn x n =
n=0 k=0 n=0 n=0
(1 + cr−1 x + · · · + c0 xr )(1 + ds−1 x + · · · + d0 xs )

with deg(p(x)q(x)) < r + s. Thus by Theorem 6.3 there exists a recurrence of ( nk=0 ak bn−k )n≥
P
of order ≤ r + s.
(3) For simplicity we restrict to the case r = s = 2. The general case can be carried over
straightforwardly. The goal is to find a recurrence of the form

x4 (an+4 bn+4 ) + x3 (an+3 bn+3 ) + · · · + x0 (an bn ), n∈N (44)

of order ≤ r + s = 4 with x0 , . . . , x4 ∈ K, not all zero.

Using the fact that an and bn satisfy c-finite recurrences of order 2, say

an+2 + c1 an+1 + c0 an = 0
bn+2 + d1 an+1 + d0 an = 0,

we can simplify the arising expressions in (44) as follows:

an+2 bn+2 = (−c1 an+1 − c0 an )(−d1 bn+1 − d0 bn )

= LinComb(an+1 bn+1 , an+1 bn , an bn+1 , an bn ).
| {z } | {z } | {z } | {z }
=h1,1 =h1,0 =h0,1 =h0,0

Similarly, we get

an+3 bn+3 = LinComb(an+2 bn+2 , an+2 bn+1 , an+1 bn+2 , an+1 bn+1 )

and using the earlier reduction

= LinComb(h1,1 , h1,0 , h0,1 , h0,0 ).

Repeating these reductions yields

an+4 bn+4 = LinComb(h1,1 , h1,0 , h0,1 , h0,0 ).

Hence (44) can be rewritten for some αi,j ∈ K as

(4) (4) (4) (4)

0 =x4 α1,1 h1,1 + α1,0 h1,0 + α0,1 h0,1 + α0,0 h0,0
(3) (3) (3) (3)

+x3 α1,1 h1,1 + α1,0 h1,0 + α0,1 h0,1 + α0,0 h0,0
(2) (2) (2) (2)

+x2 α1,1 h1,1 + α1,0 h1,0 + α0,1 h0,1 + α0,0 h0,0
(1) (1) (1) (1)

+x1 α1,1 h1,1 + α1,0 h1,0 + α0,1 h0,1 + α0,0 h0,0
(0) (0) (0) (0)

+x0 α1,1 h1,1 + α1,0 h1,0 + α0,1 h0,1 + α0,0 h0,0
15
On the right-hand side factors might cancel which could reduce the recurrence order.

70
 || recollecting

(4) (3) (2) (1) (0)

h1,1 α1,1 x4 + α1,1 x3 + α1,1 x2 + α1,1 x1 + α1,1 x0
(4) (3) (2) (1) (0)

+h1,0 α1,0 x4 + α1,0 x3 + α1,0 x2 + α1,0 x1 + α1,0 x0
(4) (3) (2) (1) (0)

+h0,1 α0,1 x4 + α0,1 x3 + α0,1 x2 + α0,1 x1 + α0,1 x0
(4) (3) (2) (1) (0)

+h0,0 α0,0 x4 + α0,0 x3 + α0,0 x2 + α0,0 x1 + α0,0 x0 .

In particular, the above equation holds if the coefficients of hi,j are zero, i.e., if
(4) (3) (2) (1) (0)
α1,1 x4 + α1,1 x3 + α1,1 x2 + α1,1 x1 + α1,1 x0 = 0
(4) (3) (2) (1) (0)
α1,0 x4 + α1,0 x3 + α1,0 x2 + α1,0 x1 + α1,0 x0 = 0
(4) (3) (2) (1) (0)
α0,1 x4 + α0,1 x3 + α0,1 x2 + α0,1 x1 + α0,1 x0 = 0
(4) (3) (2) (1) (0)
α0,0 x4 + α0,0 x3 + α0,0 x2 + α0,0 x1 + α0,0 x0 = 0

⇕
 (4) (3) (2) (1) (0)
 x4
 
0
α1,1 α1,1 α1,1 α1,1 α1,1
 (4) (3) (2) (1) (0)   x3  0
α1,0 α1,0 α1,0 α1,0 α1,0     
(0)  x2  0
=
 (4) (3) (2) (1)
  
α0,1 α0,1 α0,1 α0,1 α0,1  x  0
(4) (3) (2) (1) (0) 1
α0,0 α0,0 α0,0 α0,0 α0,0 x0 0
holds. In other words we have to solve a linear system with given αi,j and the unknowns
x0 , . . . , x4 . Let us lean back: we are given a linear system with 4 equations and 5 unknowns.
Applying the Gauss method to such a system we will always compute a non-trivial solution
0 ̸= (x4 , x3 , x2 , x1 , x0 ) ∈ K5 ! Going backwards the above arguments, it follows that we can
compute a non-trivial recurrence (44) whose order is 4 or less (if x4 = 0).
Note that the same argument can be applied to (1)–(2), that we proved differently, and to (4)
and (5) that we leave as a fun-exercise.

71
Lecture from June 18, 2024

7 Holonomic sequences and power series

Most sequences are not c-finite. One of the simplest examples are the harmonic numbers Hn .
Its generating function is
∞
X 1
Hn xn = − log(1 − x) ∈
/ K(x)
n=0
1−x

(compare (13)), and thus it cannot be c-finite by Theorem 6.3. As already elaborated in
Remark 4.5 the recurrence
1
Hn+1 − Hn =
n+1
can be turned to a homogeneous version:

(n + 2)Hn+2 − (2n + 3)Hn+1 + (n + 1)Hn = 0.

In other words, Hn satisfies a linear recurrence, not with constant coefficients (c-finite), but
with polynomial coefficients in K[n]. Such sequences are also called holonomic sequences.

Definition 7.1. (an )n≥0 ∈ KN is called holonomic (of order r and degree d) if there exist
polynomials p0 (x), p1 (x), . . . , pr (x) ∈ K[x] with 0 ̸= pr (x) and deg(pi ) < d for 0 ≤ i ≤ r such
that
pr (n) an+r + pr−1 (n) an+r−1 + · · · + p0 (n) an = 0 (n ∈ N).

In Section 3.2 we used the inhomogeneous recurrence

1
Hn+1 = Hn +
n+1
with H0 = 0 to determine the inhomogeneous 0-order linear differential equation
1
H(x) = − log(1 − x)
1−x
where the right hand-side is non-trivial. Let us repeat the game with a slight variation by using

(n + 1)Hn+1 − (n + 1)Hn − 1 = 0.

72
This gives
∞
X
0= ((n + 1)Hn+1 − (n + 1)Hn − 1) xn
n=0
∞
X ∞
X ∞
X ∞
X
n n n
= (n + 1)Hn+1 x − nHn x + Hn x − xn
|n=0 {z } |n=0 {z } |n=0 {z } |n=0
{z }
H ′ (x) ∞ H(x) 1
X 1−x
nHn xn
n=1
| {z }
X∞
x nHn xn−1
n=1
| {z }
xH ′ (x)
1
= (1 − x)H ′ (x) − H(x) −
1−x
⇕
(1 − x)2 H ′ (x) − (1 − x)H(x) = 1.
In other words, we obtain a first-order inhomogeneous linear differential equation. Similarly to
the recurrence case (see Remark 4.5 using the shift operator) we can turn this equation to a
homogeneous version by applying the differential operator Dx . In this way we get

−2(1 − x)H ′ (x) + (1 − x)2 H ′′ (x) + H(x) − (1 − x)H ′ (x) = 0

or equivalently
(1 − x)2 H ′′ (x) − 3(1 − x)H ′ (x) + H(x) = 0. (45)
This gives rise to the following definition.

Definition 7.2. A(x) = ∞ n

P
n=0 an x ∈ K[[x]] is holonomic (of order r and degree d) if there
exist polynomials q0 (x), . . . , qr (x) ∈ K[x] with qr (x) ̸= 0 and deg(qi ) ≤ r for 1 ≤ i ≤ r such that

qr (x)Dxr A(x) + qr−1 (x)Dxr−1 A(x) + · · · + a0 (x)Dx0 A(x) = 0.

In other words, given the holonomic sequence Hn , also its generating function H(x) is holo-
nomic, i.e., satisfies a homogeneous linear differential equation with polynomial coefficients.
More generally, we obtain the following result.

Theorem 7.3. Let A(x) = ∞ n

P
n=0 an x ∈ K[[x]]. Then the following holds:

1. If (an )n≥0 is holonomic of order r and degree d, then A(x) is holonomic of order ≤ r + d
and degree ≤ r + d.

2. If A(x) ∈ K[[x]] is holonomic of order r and degree d, then (an )n≥0 is holonomic of order
≤ r + d and degree ≤ r.

73
Proof. Apply the classical method. The proof is algorithmic and the resulting algorithms are
implemented in the package GeneratingFunctions.m.

Example 7.4. We start with the recurrence of the harmonic numbers an = a[n] = Hn
In[17]:= rec = a[n + 1] − a[n] == 1/(n + 1);
P∞
and compute a linear differential equation for A(x) = A[x] = n=0 an xn (= H(x)) by using the
package
In[18]:= << RISC‘GeneratingFunctions‘

Package GeneratingFunctions version 0.8 written by Christian Mallinger Copyright Research

Institute for Symbolic Computation (RISC), Johannes Kepler University, Linz, Austria

In[19]:= de = RE2DE[rec, a[n], A[x]]

Out[19]= 1 − (−1 + x)A[x] − (1 − 2x + x2 )A′ [x] == 0

As carried out above, we can compute its homogeneous version (see (45)):
In[20]:= de = Collect[D[de[[1]], x], {A[x], A′ [x], A′′ [x]}] == 0

Out[20]= −A[x] + (3 − 3x)A′ [x] + (−1 + 2x − x2 )A′′ [x] == 0

Note that we can go back to the coefficient (sequence) level. Given the differential equation de
for A(x) we can compute a recurrence for its coefficients an :
In[21]:= DE2RE[de, A[x], a[n]]

Out[21]= −(1 + n)2 a[n] + (1 + n)(3 + 2n)a[1 + n] − (1 + n)(2 + n)a[2 + n] == 0

Removing the common factor 1 + n gives

(n + 2)an+2 − (2n + 3)an+1 + (n + 1)an = 0

which is nothing else than the already found recurrence (21) of an = Hn .

an+1
Example 7.5. We start with an = n! and obtain with an
= n + 1 the linear recurrence
In[22]:= rec = a[n + 1] − (n + 1)a[n] == 0;
P∞
Given this recurrence, we can compute a linear differential equation for A(x) = n=0 an xn by
In[23]:= de = RE2DE[rec, a[n], A[x]]

Out[23]= −A[x] − (−1 + 3x)A′ [x] − x2 A′′ [x] == 0

Conversely, given the linear differential equation de for A(x), we can rediscover the linear
recurrence for an :
In[24]:= DE2RE[de, A[x], a[n]]

Out[24]= (n + 1)a[n + 1] − (n + 1)2 a[n] == 0

after removing the common factor n + 1.

In some instances one can derive as starting point a linear differential equation for a power
series. In other instances one finds algebraic (polynomial) relations.

74
Definition 7.6. A formal power series y(x) ∈ K[[x]] is called algebraic if there are polynomials
p0 (x), . . . , pd (x) ∈ K[x] with yd (x) ̸= 0 such that
pd (x)y d (x) + pd−1 (x)y(d)d−1 + · · · + p0 y(x)0 = 0.
Example 7.7. The generating function t(x) = ∞ n
P
n=0 tn x with (14) is algebraic; it satisfies the
linear differential equation (15):
x t(x)2 − t(x) + 1 = 0.
Example 7.8. The power series
∞ 1
√ X
y(x) = 1+x= 2 xn ∈ Q[[x]]
n=0
n

is algebraic; we have
y(x)2 − (x + 1)y(x)0 = 0.
HW 53. Show that the power series ex is not algebraic.
We are now ready to present closure properties for holonomic power series.
Theorem 7.9. Let A(x) = ∞
P n
P∞ n
n=0 an x , B(x) = n=0 bn x ∈ K[[x]] be holonomic. Then the
following formal power series in K[[x]] are also holonomic:
1. αA(x) + βB(x) = ∞ n
P
n=0 (αan + βbn )x for α, β ∈ K [addition];

2. A(x)B(x) = ∞
P n
Pn
n=0 x k=0 ak bn−k [Cauchy product];
P∞
3. A(x) · B(x) = n=0 (an bn )xn [Hadamard product];
4. A(B(x)) = ∞ n
P
n=0 an B(x) if B(x) is algebraic with B(0) = 0 [substitution];

5. Dx A(x) = ∞ n
P
n=0 (n + 1)an+1 x ;

6. x A(x)dx = ∞ an−1 n
R P
n=1 n x ;
P∞ n Pn 1
7. n=0 x k=0 an (= A(x) 1−x ) [indefinite summation];
P∞ an n
8. n=0 n! x [Borel transform];
P∞ n
9. n=0 n! an x [inverse Borel transform].

In addition,
10. (ad n+k )n≥0 with d, k ∈ N is holonomic [dissection];
(0) (1) (r−1)
11. if (an )n≥0 , (an )n≥0 , . . . , (an )n≥0 ∈ KN are holonomic, then its interlacing of the r
sequences, i.e.,
(0) (1) (2) (r−1) (0) (1) (2) (r−1) (0) (1) (2) (r−1)
(b0 , b0 , b0 , . . . , b0 , b1 , b1 , b1 , . . . , b1 , b2 , b2 , b2 , . . . , b2 , . . . )
| {z } | {z } | {z }
first entry second entry third entry
of each sequence of each sequence of each sequence
is holonomic.

75
The underlying proofs follow the tactic as carried out in the proof for item (3) of Theorem 6.8;
see page 70. They are all algorithmic and the corresponding algorithms are implemented within
the package GeneratingFunctions. In the following we will illustrate this powerful toolbox by
numerous examples.
Example 7.10. Compute a linear differential equation for
∞
X
x
e + n!xn ∈ K[[x]].
n=0

We get immediately a linear differential equation for ex , namely,

In[25]:= de1 = y′ [x] − y[x] == 0
P∞
Next, we compute a linear differential equation for n=0 n!xn (compare Example 7.5):
In[26]:= rec = a[n + 1] − (n + 1)a[n] == 0;

In[27]:= de2 = RE2DE[rec, a[n], y[x]]

Out[27]= −y[x] − (−1 + 3x)y′ [x] − x2 y′′ [x] == 0

Finally, we compute a linear differential equation for

∞
X
x
y(x) = e + n!xn
n=0

by executing
In[28]:= DEPlus[de1, de2, y[x]]

Out[28]= −(3 + 5x + x2 )y[x] − (−3 − 8x + 10x2 + 3x3 )y′ [x] − (3x − 11x2 + x4 )y′′ [x] + (3x3 + x4 )y′′′ [x] == 0

Similarly, we compute a linear differential equation for

∞
X
x
y(x) = e n!xn ∈ K[[x]]
n=0

by executing
In[29]:= DECauchy[de1, de2, y[x]]

Out[29]= (2 − 3x + x2 )y[x] − (1 − 3x + 2x2 )y′ [x] + x2 y′′ [x] == 0

Example 7.11. Show that the following formal power series is holonomic:
∞ n  3 2
!
X X n
Y (x) = xn ∈ K[[x]]. (46)
n=0 k=0
k

(i) By the Hadamard product (item (3) of Theorem 7.9) y(x) is holonomic if
∞ n  3 ∞ n
X
n
X n X
3 n
X 1 1
A(x) = x = n! x
n=0 k=0
k n=0 k=0
k! (n − k)!3
3

76
is holonomic.
(ii) Using the inverse Borel transform (item (9) of Theorem 7.9) three times it follows that A(x)
is holonomic if !2
∞ n ∞
X X 1 1 X 1
B(x) = xn 3 (n − k)!3
= 3
xn
n=0 k=0
k! n=0
n!
is holonomic.
(iii) Using the Cauchy product (item (2) of Theorem 7.9)) it follows that B(x) is holonomic if
∞
X 1 n
C(x) = x
n=0
n!3

is holonomic.
(iv) By applying the Borel transform three times (item (8) of Theorem 7.9)) it follows that
C(x) is holonomic if
∞
X 1
D(x) = xn =
n=0
1−x
is holonomic, which is clearly the case. Thus going backwards, also Y (x) is holonomic.

Any algebraic formal power series is also holonomic, i.e., from an algebraic relation one can
determine a linear differential equation.
Corollary 7.12. If y(x) = ∞ n
P
n=0 an x is algebraic, then y(x) is holonomic.

Proof. Define B(x) := y(x) − y(0) which again is algebraic with B(0) = 0. Thus with A(x) = x
and item (4) of Theorem 7.9 it follows that A(B(x)) = B(x) is holonomic. In particular,
y(x) = B(x) + y(0) is holonomic.
Example 7.13. We show that
x
y(x) = exp( √ ) ∈ K[[x]]
1 − 4x
is holonomic. More precisely, we start with the inner power series
x
B(x) = √ ∈ K[[[x]]
1 − 4x
and observe that it is algebraic. More precisely, we have
x2
B(x)2 = ⇔ (1 − 4x)B(x)2 − x2 B(x)0 = 0.
1 − 4x
Since A(x) = exp(x) = ex ∈ K[[x]] is holonomic with

A′ (x) − A(x) = 0,

it follows with part (4) of Theorem 7.9 that also y(x) = A(B(x)) is holonomic. Using again
the package GeneratingFunctions we can compute a linear differential equation for y(x) by
executing

77
In[30]:= de = y′ [x] − y[x] == 0;

In[31]:= ACompose[de, (1 − 4x)y[x]2 − x2 == 0, y[x]]

Out[31]= (−1 + 6x − 12x2 + 8x3 )y[x] + 4(−1 + 9x − 24x2 + 16x3 )y′ [x] + (1 − 14x + 72x2 − 160x3 + 128x4 )y′′ [x] == 0

Together with parts (10) and (11) of Theorem 7.9 we obtain the following generalization16 of
Theorem 6.8:

Corollary 7.14. Let (an )n≥0 , (bn )n≥0 ∈ KN be holonomic. Then the following sequences are
holonomic:

1. (α an + β bn )n≥0 for α, β ∈ K;

2. ( nk=0 ak bn−k )n≥0 [Cauchy product];

P

3. ( nk=0 ak )n≥0 [indefinite summation];

P

4. (an · bn )n≥0 [Hadamard product].

Proof. If (an )n≥0 , (bn )n≥0 ∈ KN are holonomic, then A(x) = ∞

P n
P∞ n
n=0 an x , B(x) = n=0 bn x ∈
K[[x]]Pare holonomic by part (1) of Theorem 7.3. Thus α A(x) + β B(x), A(x) B(x), A(x) · B(x)
∞ n
Pn
and n=0 x k=0 ak are holonomic power series. Thus by part (2) of Theorem 7.3 their
coefficients are holonomic which proves items (1)–(4) of this theorem.

Example 7.15. We present an alternative tactic to show that (46), i.e.,

∞ n  3 2
!
X X n
Y (x) = xn
n=0 k=0
k

is holonomic.
(i) We apply part (1) of Theorem 7.3 and it follows that Y (x) is holonomic if
n  3 2
!
X n
an =
k=0
k

is holonomic.
(ii) Using the Hadamard operation (item (4) of Corollary 7.14) it follows that this is the case if
n  3 n
X n X 1 1
bn = = n!3
k=0
k k=0
k!3 (n − k)!3

is holonomic.
(iii) Using again the Hadamard operation (item (4) of Corollary 7.14) it follows that this is the
case if n
X 1 1
cn =
k=0
k! (n − k)!3
3

16
A c-finite sequence is holonomic.

78
is holonomic.
(iv) Using the Cauchy product (item (2) of Corollary 7.14) it follows that this is the case if
1
dn =
n!3
is holonomic, which is clearly the case. Hence going backwards, also y(x) is holonomic. More
precisely, we can carry out the following calculations:
Step (iv): We insert a linear recurrence for dn = y[n]:
In[32]:= recD = (n + 1)3 y[n + 1] − y[n] == 0;

and compute a recurrence for cn = y[n]:

In[33]:= recC = RECauchy[rec, rec, y[n]]

Out[33]= −8y[n] − (1 + n)(16 + 21n + 7n2 )y[1 + n] + (1 + n)(2 + n)5 y[2 + n] == 0

Step (iii): Next, we compute a recurrence for bn = y[n]:

In[34]:= recH = y[n + 1] − (n + 1)3 y[n] == 0;

In[35]:= recB = REHadamard[recC, recH, y[n]]

Out[35]= −8(1 + n)2 y[n] + (−16 − 21n − 7n2 )y[1 + n] + (2 + n)2 y[2 + n] == 0

Step (ii): Now we are ready to compute a recurrence for an = y[n]:

In[36]:= recA = REHadamard[recB, recB, y[n]]

Out[36]= 512(1 + n)4 (44 + 35n + 7n2 )y[n] − 8(16 + 21n + 7n2 )(832 + 1740n + 1347n2 + 456n3 + 57n4 )y[1 + n] − (44 + 35n + 7n2 )(832 +
1740n + 1347n2 + 456n3 + 57n4 )y[2 + n] + (3 + n)4 (16 + 21n + 7n2 )y[3 + n] == 0
P∞
Finally, we can compute a linear differential equation for Y (x) = n=0 y[n]xn :
In[37]:= de = RE2DE[recA, y[n], Y[x]]

Out[37]= 45056Y[x] + 4096(−52 + 1021x)Y′ [x] + 256(−143 − 17450x + 121600x2 )Y′′ [x] + 16(27 − 21534x − 940504x2 + 3712256x3 )Y′′′ [x] +
4(596x − 162403x2 − 3978656x3 + 10685056x4 )Y(4) [x] + 3(925x2 − 137452x3 − 2270272x4 + 4567552x5 )Y(5) [x] + (1073x3 −
105702x4 −1298880x5 +2076160x6 )Y(6) [x]+14(11x4 −798x5 −7752x6 +10240x7 )Y(7) [x]+7(x5 −57x6 −456x7 +512x8 )Y(8) [x] == 0

HW 54. Compute a holonomic recurrence for

∞
X
n x
an = [x ]e Hn xn .
n=0

HW 55. Compute a holonomic recurrence for

n   
X n n
an = .
k=0
k n − k

HW 56. Compute a holonomic differential equation for

∞ n
!
X X
a(x) = sin(x) k! xn .
n=0 k=0

79
If a formal power series is invertible, then in most instances the inverse power series is not
holonomic. However, finding such a proof is highly non-trivial. But some instances the following
theorem is helpful.
1
Theorem 7.16. Let y(x) ∈ C[[x]] be holonomic with y(0) ̸= 0. Then y(x)
is holonomic if and
y ′ (x)
only if y(x)
is algebraic.
1
HW 57. Show that y(x) = cos(x) is not holonomic.
[Hint: one may use that fact that tan(x) is not algebraic.]

80
Lecture from June 25, 2024

8 Symbolic Summation (a short introduction)

In the previous lectures we have seen already applications in symbolic summation. For instance,
we discovered and proved the identity
A 2k −2−2k+2n −2+2n 2A −2−2A+2n






X k −1−k+n
(−1 + 2n) −1+n
(1 + 2A)(2 + 2A − n) A −1−A+n
= +
k=0
(1 + k)(−k + n) n(1 + n) (1 + A)n(1 + n)

for n ≥ 0 and 0 ≤ A ≤ n on page 37. In particular, the specialization to A = n lead to (18),

i.e.,
  X n−1    
1 2n 1 2k 1 2n − 2k − 2
= .
n+1 n k=0
k + 1 k n − k n − k − 1
Similarly, we focused on the verification of such identities in Remark 4.4.
In the following, we will give some more ideas how such identities can be discovered and will link
it to various examples coming from the last lectures. We start with the following telescoping
problem:
Given an expression f (k) that evaluates to a sequence.
Find an expression g(k) such that the telescoping equation

f (k) = g(k + 1) − g(k) (47)

holds.
Suppose we find such an expression g(k). Then we can follow the idea given in HW 3. Namely,
summing (??) over k from a to b (and assuming that no poles arise during the evaluation)
yields
Xb
f (k) = g(b + 1) − g(a). (48)
k=a

We note that we could always choose

k−1
X
g(k) = f (i) (49)
i=a

which would turn (??) to the trivial identity bk=a f (k) = bk=a f (k).
P P

Thus we should refine our problem from above:

Find an expression g(k) with (??) where g(k) is simpler than the trivial solution (??).

81
8.1 Indefinite summation of polynomials
We start with one of the most simplest cases: the summand is a polynomial, i.e., f (x) ∈ K[x].
The following questions arise:

1. What is the domain of expressions in which we search g(k)?

2. How can we calculate a solution g(k) in this solution domain?

As it turns out, the first question can be answered nicely: a solution g(x) exists always in K[x].
For the second question, we will consider two different tactics that are often used in summation
packages.
• Tactic 1: the classical approach. In the following it will be convenient to use also the difference
operator. For any sequence (expression) g(k) we define

∆g(k) := g(k + 1) − g(k).

Note that for indefinite integration of polynomials one can utilize the following well known
property: for any m ∈ N we have
Dx xm = m xm−1 (50)
which implies
b
xm+1 bm+1 − am+1
Z b
xm dx = = . (51)
a m+1 a m+1
Thus by linearity we can integrate any polynomial by
d
Z bX d b d
cm (bm+1 − am+1 )
X Z X
m m
cm x dx = cm x dx = . (52)
a m=0 m=0 a m=0
m + 1

For indefinite summation of polynomials we can follow precisely the same classical strategy
which is based on the following lemma.

Lemma 8.1. For m ∈ N we have

∆xm = m xm−1 .

Proof. We have

∆xm = (x + 1)m − xm
= (x + 1)x(x − 1) . . . (x − m + 2) − x(x − 1) . . . (x − m + 1)
= ((x + 1) − (x − m + 1))x(x − 1) . . . (x − m + 2)
= m xm−1 .

82
As a consequence we get
xm+1
= xm , m ∈ N
∆
m+1
and summing this equation over k from a to b yields
b
X (b + 1)m+1 − am+1
m
x = .
x=a
m+1

Note that this is nothing else than the discrete version given in (??) and (??). In particular,
for given
Xd
f (x) = cm xm ∈ K[x] (53)
m=0

with d ∈ N it follows that

d
X cm xm+1
g(x) =
m=0
m+1
is a telescoping solution of (??). Furthermore, analogously to (??) we obtain
b d b d
X X X X cm ((b + 1)m+1 − am+1 )
f (x) = cm xm = .
x=a m=0 x=a m=0
m + 1

The only problem is that in many cases one does not have a polynomial given in the represen-
tation (??) for some d ∈ N but in the form
d
X
c̄m xm ∈ K[x].
m=0

Luckily one can rewrite a polynomial written in the basis

1, x, x2 , . . . , xd

to the representation written in the basis

x0 = 1, x1 = x, x2 = x(x − 1), . . . , xd = x(x − 1) . . . (x − d + 1)

by using the formula

m
X
xm = S(m, k)xk
k=0

where S(n, k) denotes the Stirling numbers of second kind. They can be computed by
k  
1 X i k
S(n, k) = (−1) (k − i)n ;
k! i=0 i

alternatively, there is a recurrence formula.

83
Example 8.2. Consider the polynomial

f (x) = x4 .

Using the formulas from above, we get

4
X
4
f (x) = x = S(4, k)xk = 0x0 + 1x1 + 7x2 + 6x3 + 1x4 .
k=0

Thus we get
1 7 3 1
g(x) = x2 + x3 + x4 + x5
2 3 2 5
1
= (x − 1)x(2x − 1)(3x2 − 3x − 1).
30
such that
g(x + 1) − g(x) = f (x)
holds. In particular we get
n n
X
4
X 1
k = f (k) = g(n + 1) − g(1) = n(n + 1)(2n + 1)(3n2 + 3n − 1). (54)
k=1 k=1
30

• Tactic 2: linear algebra. We use the following property: for f (x) ∈ K[x] there is a g(x) ∈ K[x]
with (??) where
deg(g) ≤ deg(f ) + 1.
Thus setting d := deg(f ) + 1 for given f ∈ K[x] the desired solution has the form
d
X
g(x) = gm xm
m=0

and we can determine the unknowns g0 , . . . , gd ∈ K by linear algebra as follows.

Example 8.3. Take f (x) = x4 ∈ Q[x]. With d = deg(f ) + 1 = 5 the ansatz

g(x) = g0 + g1 x + g2 x2 + g3 x3 + g4 x4 + g5 x5

for the unknowns g0 , g1 , g2 , g3 , g4 , g5 ∈ Q is in place. This gives

x4 =∆g(x) = g(x + 1) − g(x)

= 0x5
+ 5g5 x4
+ (4g4 + 10g5 )x3
+ (3g3 + 6g4 + 10g5 )x2
+ (2g2 + 3g3 + 4g4 + 5g5 )x
+ (g1 + g2 + g3 + g4 + g5 )x0 .

84
By coefficient comparison this yields the linear system

[x4 ] 1 =5g5
[x3 ] 0 =4g4 + 10g5
[x2 ] 0 =3g3 + 6g4 + 10g5
[x1 ] 0 =2g2 + 3g3 + 4g4 + 5g5
[x0 ] 0 =g1 + g2 + g3 + g4 + g5

which is already in triangular form. Thus we can read off the solution
1 1 1 1
g5 = , g4 = − , g3 = , g2 = 0, g1 = − , g0 = c
5 2 3 30
with c ∈ Q. In particular, we can choose c = 0 and obtain
x5 x4 x3 x 1
= (x − 1)x(2x − 1) 3x2 − 3x − 1 .


g(x) = − + −
5 2 3 30 30
To this end, we continue as in the previous example and get (??).

8.2 More general summation objects for indefinite and definite sum-
mation
8.2.1 Telescoping

Clearly, the first tactic is very elegant, but it works only for the special case of polynomial
summation. For the second tactic one has to work more (i.e., has to solve in addition a linear
system), but it turns out to be more general. More precisely, one can carry over these ideas to a
rather general setting that works not only for the polynomial ring Q[x] but in more general rings
called RΠΣ-difference rings that have been implemented within the summation package Sigma.
In the following all technical details are omitted and we proceed with a concrete example.
Example 8.4. We want to sum
n
X
Hk ;
k=0

compare Remark 4.4. In order to accomplish this task, we take

f (k) = Hk

and search for

g(k) ∈ Q(k)[Hk ]
with
f (k) = g(k + 1) − g(k). (55)
Here we can use a similar tactic as used in the case of polynomial summation. Namely, sum-
mation theory tells us that any such solution g(k) has the property

deg(g) ≤ deg(f ) + 1 = 1 + 1 = 2.

85
As a consequence we can make the ansatz

g(k) = g0 (k)Hk0 + g1 (k)Hk1 + g2 (k)Hk2

with g0 (k), g1 (k), g2 (k) ∈ Q(k). Using recursive algorithms and linear system solving (details
are skipped here) we find

g0 (k) = −k
g1 (k) = k
g2 (k) = 0,

i.e.,
g(k) = −k + kHk + 0Hk2 .
Hence summing (??) over k from 0 to n gives
n
X
Hk = g(n + 1) − g(0) = (n + 1)Hn+1 − (n + 1) = −n + (1 + n)Hn .
k=0

The above machinery can be carried out within the summation package Sigma. After loading
it into Mathematica
In[38]:= << Sigma.m
Sigma - A summation package by Carsten Schneider © RISC-JKU

one can insert the above sum

In[39]:= mySum = SigmaSum[SigmaHNumber[k], {k, 0, 1}]
n
X
Out[39]= Hk
k=0

and can apply the command

In[40]:= SigmaReduce[mySum]

Out[40]= −n + (1 + n)Hn

In general one can insert, e.g., a sum of the form

n
X
f (k) (56)
k=l

with l ∈ N where f (k) itself is given in terms of indefinite nested sums defined over hypergeo-
metric products.
Definition 8.5. Let K be a field. A product kj=l f (j), l ∈ N, is called hypergeometric in k
Q
over K if f (x) ∈ K(x) is a rational function where the numerator and denominator of f (j)
are nonzero for all j ∈ Z with j ≥ l. An expression in terms indefinite of nested sums over
hypergeometric products in k over K is composed recursively by the three operations (+, −, ·)
with

• elements from the rational function field K(k),

86
 • hypergeometric products in k over K,
• and sums of the form
Pk
j=l f (j) with l ∈ N where f (j) is an expression in terms of
indefinite nested sums over hypergeometric products in j over K; here it is assumed that
the evaluation of f (j) for all j ≥ l does not introduce any poles.
Restricting to the case that f (k) in (??) is only a hypergeometric product, one may use Gosper’s
algorithm (1978). For the general class of indefinite nested sums defined over hypergeometric
products the difference field approach built into Sigma can be used. The underlying algorithms
are inspired by Karr’s summation algorithm (1981) and contain many enhancements and gen-
eralizations. In the following we present examples that illustrate some of these features.
Inserting the sum arising on page 13
n−1
X 2k
In[41]:= mySum = ;
k=0
(k + 1)(k + 2)

we get the result

In[42]:= SigmaReduce[mySum]
−1+n
2(−1 + n)(1 + 2n) X 1
Out[42]= − +2
n(1 + n) i
i =1 11

which yields the identity given in (3). Internally, Sigma takes the summand
2k
f (k) = ∈ Q(k)
(k + 1)(k + 2)
and computes a solution g(k) of the telescoping equation (??). Note that g(k) does not exist
in Q(k) but in the more general domain
k k
4k X 1 hX 1i
g(k) = − +2 ∈ Q(k) (= Q(k)[Hk ])
1+k i=1
i i=1
i

which has been derived automatically by Sigma.

Other examples are
In[43]:= mySum = mySum = SigmaSum[SigmaPower[−1, k]SigmaBinomial[n, k]SigmaHNumber[k], {k, a, b}]
b
X n
Out[43]= (−1)k Hk
k=a
k

In[44]:= SigmaReduce[mySum]
(a − n)(−1 + a − n) (−1 + a − n)Ha
 n  −b + n (−b + n)Hb
n
Out[44]= + (−1)1+a + + (−1)b
an2 n −1 + a n2 n b

or
In[45]:= mySum = SigmaSum[SigmaSum[SigmaBinomial[n, k], {k, 0, r}]2 , {r, 0, b}]
b r  
X X n
2
Out[45]=
r=0 k=0
k

In[46]:= SigmaReduce[mySum]
n Xb   b   b
n 1 X n
2 1 X  n 2
Out[46]= (−b + n) + (2 + 2b − n) − n
b i =0 i1 2 i =0
i1 2 i =0 i1
1 1 1

87
8.2.2 Recurrence finding (creative telescoping)

We can play this fun-game for many summation problems. However, sooner or later one ends
up at examples with the following behavior:
In[47]:= mySum = SigmaSum[SigmaBinomial[n, k], {k, 0, a}]
a  
X n
Out[47]=
k=0
k

In[48]:= SigmaReduce[mySum]
a  
X n
Out[48]=
i1 =0
i1

This means that Sigma (but also, e.g., Gosper’s algorithm which is applicable for this input)
fails. In short, there does not exist a solution g(k) of
 
n
= g(k + 1) − g(k)
k

where g(k) is simpler than the input sum ki=0 ni .

P

Such sums seem hopeless. However, in this particular example we have not used the fact that the
sum contains an extra discrete parameter n. Due to Zeilberger’s powerful creative telescoping
paradigm (introduced 1990) such sums (more precisely definite sums where we specialize the
summation bound a, e.g., to n) can be handled in the following way.

Example 8.6. We consider the sum

n
X
S(n) = f (n, k)
k=0

with  
n
f (n, k) = .
k
Pk n


As mentioned above, one first tries to find an expression g(n, k) being simpler than i=0 i
such that
g(n, k + 1) − g(n, k) = f (n, k)
holds; as observed above, we fail with this tactic. Precisely here the creative telescoping tactic
starts: one proceeds by looking for such an expression g(n, k) together with a constant c1 (n),
free of k, such that

g(n, k + 1) − g(n, k) = f (n, k) + c1 (n) f (n + 1, k) (57)

holds. In this particular instance we find

   
1 k n 1 n
c1 (n) = −1/2, g(n, k) = , g(n, k + 1) = .
2n−k+1 k 2 k

88
Now we repeat the game as for the telescoping case. We sum (??) over k from 0 to n and get
n n
X 1 X
g(n, n + 1) − g(n, 0) = f (n, k) − f (n + 1, k)
| {z } | {z }
k=0
2 k=0
1 0
2 | {z } | {z }
S(n) Xn+1
f (n + 1, k) − f (n + 1, n + 1)
| {z }
|k=0 {z } 1

S(n+1)

⇕
S(n + 1) − 2S(n) = 0.
Using this recurrence together with the initial value S(0) = 1 we discover the simplification
n  
X n
S(n) = = 2n (58)
n=0
k

which is nothing else than the binomial theorem. Within Sigma this mechanism can be carried
out as follows. We insert our sum
In[49]:= mySum = SigmaSum[SigmaBinomial[n, k], {k, 0, n}]
n  
X n
Out[49]=
k=0
k

and compute a linear recurrence with the function call

In[50]:= rec = GenerateRecurrence[mySum, n][[1]]

Out[50]= 2SUM[n] − SUM[n + 1] == 0

Example 8.7. Similarly, we can compute a recurrence for the definite sum
In[51]:= mySum = SigmaSum[SigmaBinomial[n, k]3 , {k, 0, n}]
n  
X n 3
Out[51]=
k=0
k

with the function call

In[52]:= GenerateRecurrence[mySum, n][[1]]

Out[52]= 8(1 + n)2 SUM[n] + (16 + 21n + 7n2 )SUM[1 + n] − (2 + n)2 SUM[2 + n] == 0

Note that this is precisely the recurrence in Out[36] on page 79. In other words, symbolic
summation provides a short-cut that enables one to skip the technical calculation steps (iv)
and (iii) in Example 7.15.

In general, we can insert within the summation package Sigma sums of the form
n
X
S(n) = f (n, k)
k=l

89
with l ∈ N and where f (n, k) is an expression in terms of indefinite nested sums defined
over hypergeometric products w.r.t. k; here the sums and products may involve also the extra
parameter n. Then fixing d ∈ N, one can search for an expression g(n, k) (which is simpler
than the input sum S(n)) together with constants c1 (n), . . . , cd (n), which may depend on n but
which are free of k, such that the following creative telescoping equation holds:

g(n, k + 1) − g(n, k) = f (n, k) + c1 (n)f (n + 1, k) + · · · + cd (n)f (n + d, k).

Here one starts usually with d = 0 (which is telescoping) and increases d = 0, 1, 2, 3, ... incre-
mentally until one finds a solution for a given d ∈ N. If one is successful, one can sum the found
creative telescoping equation over k and obtains a linear recurrence of order d of the form

S(n) + c1 (n)S(n + 1) + · · · + cd (n)S(n + d) = h(n). (59)

8.2.3 Recurrence solving (in terms of d’Alembertian solutions)

In most cases the found recurrence (??) is built by c1 (n), . . . , cd (n) which are rational functions
in n and h(n) can be simplified again to indefinite nested sums defined over hypergeometric
products. At this point we utilize another strong tool of Sigma
Given such a recurrence, Sigma can find all solutions that can be expressed again within the class
of indefinite nested sums defined over hypergeometric products (such solutions are also called
d’Alembertian solutions). Internally, Petkovšek’s Hyper algorithm (1992) and a generalized
version of it has been implemented.

Example 8.8. [Cont. of Example ??] Given the recurrence rec from Out[??] one can solve it
with the function call
In[53]:= recSol = SolveRecurrence[rec, SUM[n]]

Out[53]= {{0, 2n }, {1, 0}}

This means that 2n is a solution of the homogeneous version of the recurrence. Finally, using
the initial value S(0) = 1, one gets the simplification (??). This last step can be also carried
out with the function call
In[54]:= FindLinearCombination[recSol, mySum, n, 1]

Out[54]= 2n

where 1 specifies the number of initial values that should be used. To obtain the correct result
this number must be at least the order of the recurrence; if it is higher, extra values are used
which gives extra robustness tests. In other words, we have derived the identity (??) fully
automatically by means of computer algebra.

This recurrence solver can be also used to solve c-finite recurrences – the solutions (see Theo-
rem 6.6) are contained within the class of hypergeometric products.

90
 Example 8.9.
In[55]:= RSolve[M[h] − 2M[h − 1] + M[h − 3] == 0, M[h], h]//FullSimplify

√  h √  h
    
 1 1
Out[55]= M[h] → c1 1− 5 + c2 1+ 5 + c3
2 2

This means that

√  h √  h
     
 1 1
c1 1− 5 + c2 1+ 5 + c3 | c1 , c2 , c3 ∈ C
2 2
provides the full solution space and thus there exist c1 , c2 , c3 ∈ C such that
√  h √  h
     
1 1
M (h) = c1 1− 5 + c2 1+ 5 + c3
2 2
holds for all h ∈ N. Finally, looking at h = 0, 1, 2 we get the linear system
1 = c1 + c2 + c3
1 √  1 √ 
2 = c1 1 − 5 + c2 1 + 5 + c3
2 2
2
√ √  2
    
1  1
4 = c1 1− 5 + c2 1+ 5 + c3 .
2 2

Solving it (using the Gauss algorithm) yields

1 √
c1 = (5 − 2 5),
5
1 √
c2 = (5 + 2 5),
5
c3 = −1.
Remark: Providing in addition the initial values to RSolve, this calculation can be carried out
in one stroke:
In[56]:= RSolve[M[h] − 2M[h − 1] + M[h − 3] == 0
&&M[0] == 1&&M[1] == 2&&M[2] == 4, M[h], h]//FullSimplify
!
√  1 √  h  √  1 √  h
   
1 
Out[56]= 5−2 5 1− 5 + 5+2 5 1+ 5 −5
5 2 2

More precisely, we get √ √

5−2 5 h 5+2 5 h
M (h) = −1 + r− + r+ . (60)
5 5
Instead of using the Mathematica-command RSolve in In[16] on page 66 one can execute the
command
In[57]:=recSol3 = SolveRecurrence[M[h] − 2M[h − 1] + M[h − 3] == 0, M[h]]
√
(−1)h ( 5 − 1)h 2h
Out[57]= {{0, 1}, {0, }, {0, √ }, {1, 0}}
2h ( 5 − 1)h

to find the full solution space:

√
(−1)h ( 5 − 1)h 2h
{c1 + c2 + c3 √ | c1 , c2 , c3 ∈ C}.
2h ( 5 − 1)h

91
Finally we use the first three initial values M (0) = 1, M (1) = 2, M (2) = 4 to derive the
corresponding constants c1 , c2 , c3 . This can be carried out with the Sigma-routine
In[58]:=FindLinearCombination[recSol3, {0, {1, 2, 4}}, h, 3]
√ √ √
5 − 2 5 (−1)h ( 5 − 1)h 5+2 5 2h
Out[58]= −1 +
h
+ √
5 2 5 ( 5 − 1)h

One can easily check (which would be another little HW) that this output is equivalent to the
found representation (41).
Alternatively, one can also insert directly the inhomogeneous recurrence from (40) and gets
In[59]:=recSol2 = SolveRecurrence[M[h] − M[h − 1] − M[h − 2] == 1, M[h]]
√
(−1)h ( 5 − 1)h 2h
Out[59]= {0,
h
}, {0, √ }, {1, −1}}
2 ( 5 − 1)h

Here we get two linearly independent solutions of the homogeneous version (indicated by a 0
in the first entry of the list), namely,
√
(−1)h ( 5 − 1)h 1
√

h
H1 (h) = (= 2
1 − 5 ),
2h
2h √

h
H2 (h) = √ (= 12 1 + 5 )
( 5 − 1)h

and one particular solution of the recurrence itself (indicated by a 1 in the first entry of the
list):
P (h) = −1.
More precisely, we get the full solution by taking all linear combinations of the homogeneous
solutions plus the derived particular solution:

V = {P (h) + c1 H1 (h) + c2 H2 (h) | c1 , c2 ∈ C}

√
(−1)h ( 5 − 1)h 2h
= {−1 + c1 + c 2 √ | c1 , c2 ∈ C}.
2h ( 5 − 1)h
Finally, we use the first two initial values that uniquely determine the constants c1 , c2 and thus
yield the closed form of M (h). Again this can be carried out by executing
In[60]:=FindLinearCombination[recSol2, {0, {1, 2}}, h, 2]
√ √ √
5 − 2 5 (−1)h ( 5 − 1)h 5+2 5 2h
Out[60]= −1 + + √
5 2h 5 ( 5 − 1)h

Example 8.10. Consider the recurrence (2), i.e.,

(n + 1)F (n + 1) − (n + 2)F (n) = 2n, n≥0

with the initial value F (0) = 0 that we derived for the analysis of QuickSort. Instead of using
the “variation of constants” method, one can also activate the recurrence solver of Sigma to
the recurrence
In[61]:= rec = (n + 1)F[n + 1] − (n + 2)F[n] == 2n;

and one gets the solution

92
In[62]:= recSol = SolveRecurrence[rec, F[n]];
n
X 1
Out[62]= {{0, 1 + n}, {1, 4 + 2(1 + n) }}
i
i =1 1
1

This means that the set of solutions (that produce sequences with entries from Q) is
n
X 1
{c (n + 1) + 4 + 2(1 + n) | c ∈ Q}.
i1 =1
i1
| {z }
Fc (n)

Finally, we determine c ∈ Q such that Fc (0) = 0 holds. In our case we have to choose c = −4
which implies
F (n) = F−4 (n), n ∈ N.
This last step can be carried out with
In[63]:= FindLinearCombination[recSol, {0, {0}}, n, 1]
n
X 1
Out[63]= −4n + 2(1 + n)
i
i =1 1
1

As a consequence, we rediscovered with computer algebra the representation (4).

8.3 Definite summation using Sigma

We conclude this section with variations of the identity (??) (see Examples ?? and ??) by
utilizing the different tools of Sigma:

1. recurrence finding with the function command GenerateRecurrence;

2. recurrence solving with the function command SolveRecurrence;

3. and combining the solutions (in case that sufficiently many solutions are found) with the
function command FindLinearCombination.

More precisely, we will simplify definite sums to alternative representations which are given in
terms of indefinite nested sums defined over hypergeometric products
Let us consider as warm up example the sum
In[64]:= mySum = SigmaSum[SigmaHNumber[k]SigmaBinomial[n, k], {k, 0, n}]
n  
X n
Out[64]= Hk
k=0
k

First, we apply the creative telescoping summation paradigm (see Example ?? for the sum
(??)) in Sigma and compute a linear recurrence of order 2:
In[65]:= rec = rec = GenerateRecurrence[mySum, n][[1]]

Out[65]= −4(1 + n)SUM[n] + 2(3 + 2n)SUM[1 + n] + (−2 − n)SUM[2 + n] == −1

Second, we solve the recurrence in terms of all solutions that are expressible in terms of indefinite
nested sums defined over hypergeometric products. In this case, we find all solutions. Namely,

93
2 linearly independent solutions of the homogeneous version (indicated by a 0 in the first entries
of the lists) and one particular solution (indicated by a 1 in the first entry of the list):
In[66]:= recSol = SolveRecurrence[rec[[1]], SUM[n]]

Out[66]= {{0, 2n }
n
X 1
{0, 2n }
i
i =1 1
1
n
n
X 2−i1
{1, −2 }}
i =1
i1
1

Third, we combine all these solutions (by considering the first 2 initial values of the input sum)
and obtain a closed-form representation:
In[67]:= sol = FindLinearCombination[recSol, mySum, n, 2]
n n
X 1 X 2−i1
Out[67]= 2n − 2n
i
i =1 1 i =1
i1
1 1

In other words, we obtain the simplification

n   n n
X n n
X 1 n
X 2−i1
Hk = 2 −2 .
k=0
k i
i =1 1 i =1
i1
1 1

Here the definite sum n  

X n
Hk (61)
k=0
k
(the summand and the summation range depend on n) is simplified to an expression in terms
of the two indefinite nested sums: n n
X 1 X 2−i1
, .
i =1
i1 i =1
i1
1 1

Raising the power of the harmonic numbers in (??), we can repeat this game to more and more
complicated calculations. Consider, e.g., the sum
In[68]:= mySum = SigmaSum[SigmaHNumber[k]3 SigmaBinomial[n, k], k, 0, n]
n  
X n 3
Out[68]= H
k=0
k k

Again we apply the creative telescoping summation paradigm in Sigma. This time we compute
a linear recurrence of order 6:
In[69]:= rec = rec = GenerateRecurrence[mySum, n][[1]]

Out[69]= −16(1 + n)(2 + n)(3 + n)(5 + n)2 (14 + 18n + 3n2 )SUM[n] +
8(2 + n)(3 + n)(4258 + 12918n + 9753n2 + 3088n3 + 444n4 + 24n5 )SUM[1 + n]
− 4(3 + n)(30368 + 145056n + 147724n2 + 66050n3 + 15043n4 + 1716n5 + 78n6 )SUM[2 + n] +
4(65124 + 531256n + 668609n2 + 373678n3 + 112942n4 + 19256n5 + 1749n6 + 66n7 )SUM[3 + n]
− (4 + n)(15448 + 315504n + 323794n2 + 135202n3 + 28273n4 + 2952n5 + 123n6 )SUM[4 + n] +
(4 + n)(5 + n)(−452 + 19704n + 15835n2 + 4700n3 + 615n4 + 30n5 )SUM[5 + n] −
(4 + n)(5 + n)(6 + n)3 (−1 + 12n + 3n2 )SUM[6 + n] == 968 + 395n − 35n2 − 30n3 − 3n4

Next, we solve the recurrence in terms of all solutions that are expressible in terms of indefinite
nested sums defined over hypergeometric products. Again we find all solutions: 6 linearly

94
independent solutions of the homogeneous version (indicated by a 0 in the first entries of the
lists) and one particular solution (indicated by a 1 in the first entry of the list):
In[70]:= recSol = SolveRecurrence[rec[[1]], SUM[n]]

Out[70]= {{0, 2n },
n
X 1
{0, 2n },
i
i =1 1 1
n
X
n 2−i1
{0, 2 },
i =1
i1
1
i1
X 2i2
2−i1
n n n i
X 1 X 1
2 X i2 =1 2

{0, 2 2
+2 −2 2n },
i
i =1 1
i
i =1 1 i =1
i1
1 1 1
i1
X 1
2−i1
n n n n i
X 2−i1 X 1
X 2−i1 X i2 =1 2

{0, − 6 2
−6 +8 2n },
i =1
i1 i
i =1 1 i =1
i1 i =1
i1
1 1 1 1
i1 i1 i1
X 2−i2 X 2i2 X 2i2
2i1 2−i1 2−i1
n n i2 n i n n i n
10 X 1 X i =1
2
X i =1 2
2
X 1 X i2 =1 2
X 1
{0, 3
−2 −6 + 6 −6
3 i =1 i1 i =1
i21 i1 =1
i21 i
i =1 1
2
i =1
i1 i
i =1 1
1 1 1 1 1
i1
i1
X 1
2
n n n n n i
14 X 1
3 X 2i1
X 2−i1 X 2−i1
X i =1 2
2
+ +2 2
−8
3 i =1 i1 i
i =1 1 i =1
i1 i =1
i1 i =1 i1
1 1 1 1 1
i1 i1 i1 i1 i1
X 1
2 X 1
X 2−i2 X 1
X 2i2
2i1 2−i1
n i2 n i2 i i2 n i i
X i2 =1 X i2 =1 2 =1
X i2 =1 2 i2 =1 2

−8 +8 +8 2n },
i1 =1
i1 i1 =1
i1 i1 =1
i1
i1 i1
X 1 X 1
2−i1 2−i1
n n i n n i n n n
X 2−i1 X i =1 2
2
X 2−i1 X i2 =1 2
X 1 5 X 1
X 2−i1
{1, − 3 3
+8 + −6 +9 +
i =1
i1 i =1
i21 i =1
2
i1 i =1
i1 i
i =1 1
2
2 i =1 i1 i =1 i1
1 1 1 1 1 1 1
i1 i1
X 1
2 X 2−i2
2
2−i1 2i1
n n n n n i n i2
7 X 1
2 X 2−i1 X 2−i1
2 X 2i1 X i =1 2
2
X i =1
2
− +3 −6 −3
2 i =1 i1 i =1 i1 i =1
i1 i
i =1 1 i =1
i1 i1 =1
i1
1 1 1 1 1
i1 i1
X 1
X 2−i2
P i1 2i2
n
X 2−i1
n
X 2−i1 i2 =1 i2
n
X i2 =1
i2 i
2 =1
i2

2n }}


−3 +
i1 =1
i1 i1 =1
i1 i1 =1
i1

Finally, we combine all these solutions (by considering the first 6 initial values of the input
sum) and obtain the closed-form representation:
In[71]:= sol = FindLinearCombination[recSol, mySum, n, 6]
i1 i1 i1
X 1 X 2−i2 X 2i2
2−i1 2i1 2−i1
n n n i n i2 n i n n
5 n X 1 X 2−i1 X i =1 2
2
X i =1
2
X i =1 2
2
X 1
X 1
Out[71]= 2 −32n +23+n −2n −32n +32n −
3 i i31 i31 i21 i21 i21 i2 i
i =1 1 i =1 1
1 =1 i 1 =1 i 1 =1 i1 =1 i1 =1 1 1
n n n n n n n n n
X 2−i1 X 1 7 n X 1
3 X 1
X 2−i1 X 2i1
X 2−i1 X 1
2 X 2−i1
321+n +52−1+n +2n −72−1+n


+ 2 +
i1 =1
i21 i1 =1
i1 3 i1 =1
i1 i1 =1
i21 i i1 i21 i1 i
i =1 1
i1
1 =1 i1 =1 i1 =1 i =1 1 1
i1 i1
i1
X 1 X 1
2
P i1 2
n n n n −i 1 n n i n i
n
X 2−i1
2 X 2i1 X 1
X 2 1 i2 =1 i2
X 2−i1
X i =1 2
2
X i =1 2
2
32 + 92n −2 2+n
− 22+n −
i =1
i1 i
i =1 1
i
i =1 1 i =1
i1 i =1
i1 i =1 i1 i1 =1
i1
1 1 1 1 1 1
i1 i1 i1 i1 i1 i1
X 1
2 X 1
X 2−i2 X 1
X 2−i2 X 2−i2
2
2−i1 2i1 2i1
n i n i i2 n i i2 n i2
X i =1 2
2
X i =1
2
2 i =1 2
X i =1
2
2 i =1 2
X i =1
2
321+n + 2n + 22+n − 32n −
i1 =1
i1 i1 =1
i1 i1 =1
i1 i1 =1
i1

95
 i1 i1 i1 i1
X 2i2 X 2i2 X 1
X 2i2
2−i1 2−i1 2−i1
n n i n n i n i i
X 1
X i =1 2
2
X 2−i1
X i =1 2
2
X i =1
2
2 i =1 2 2
32n − 32n + 22+n
i
i =1 1 i =1
i1 i =1
i1 i =1 i1 i1 =1
i1
1 1 1 1

We note that the arising sums

n n n n n n n n n −i
Pi 1 1
X 1 X 1 X 1 X 2−i1 X 2−i1 X 2−i1 X 2i1 X 2i1 X 2 1 i2 =1 i2
, , , , , , , , ,
i3 i2 i
i =1 1 i =1 1 i =1 1 i =1
i31 i =1 i21 i =1 i1 i =1 i21 i =1 i1 i =1 i21
1 1 1 1 1 1 1 1 1
i1 i1 i1 i1 i1
−i1
X 1 i1
X 1 X 1
2 −i1
X 1
2 i1
X 2−i2
2 2 2 2
X n i X
i2 =1 2
n i X
i2 =1 2
n
i2 =1 2
i X n i
i2 =1 2
X n
i2 =1
i2
, , , , 2
,
i =1
i1 i =1
i 1 i =1
i1 i =1
i 1 i =1
i 1
1 1 1 1 1
i1 i1 i1 i1 i1 i1
X 1
X 2−i2 X 1
X 2−i2 X 2−i2
2 −i1
X 2i2
2i1 2i1 2
n
i2
i
=1 2 i
i 2
n i
=1 2 i
i2
n i2 n i
i2 =1 2
2 =1 i2 2 =1 i2 =1
X X X X
, , , ,
i1 =1
i1 i1 =1
i1 i1 =1
i1 i =1
i21
1
i1 i2 i1 i1 i2
X 2 X 1
X 2
2−i1 2−i1
n
X i
i2 =1 2
X n
i2
i
=1 2 i
i
=1 2
2
,
i1 =1
i1 i =1
i1
1

are again indefinite nested while the input sum

n  
X n
Hk3
k=0
k

is definite: the summand and the summation range depend on n.

96