CMSC 250: Sequences, Sums, Products,
Recursively Defined Sets and Binary Trees
Justin Wyss-Gallifent
November 2, 2021
1 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1 Intuition and Formal Definition . . . . . . . . . . . . . . . 2
1.2 Traditional Notation . . . . . . . . . . . . . . . . . . . . . 2
1.3 Recursive Sequences . . . . . . . . . . . . . . . . . . . . . 3
1.4 Conversion Between Definitions . . . . . . . . . . . . . . . 3
1.5 Shifting Starting Indices . . . . . . . . . . . . . . . . . . . 4
2 Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Evaluation – Just Do It! . . . . . . . . . . . . . . . . . . . 5
2.3 Special Case Formulas . . . . . . . . . . . . . . . . . . . . 5
2.4 Telescoping Sums . . . . . . . . . . . . . . . . . . . . . . . 8
3 Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Evaluation – Just Do It! . . . . . . . . . . . . . . . . . . . 9
3.3 Telescoping Products . . . . . . . . . . . . . . . . . . . . . 9
4 Recursively Defined Sets . . . . . . . . . . . . . . . . . . . . . . . 10
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5 Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2 Recursive Definition . . . . . . . . . . . . . . . . . . . . . 12
5.3 Properties of Binary Trees . . . . . . . . . . . . . . . . . . 13
1
1 Sequences
1.1 Intuition and Formal Definition
Sequences of numbers arise all over the place in both mathematics and computer
science, in both limits and for loops.
Informally a sequence is just an infinite list of numbers, one after another.
Example 1.1. Here are some examples:
1, 2, 3, 4, … Looks like it increases by 1 each time!
42, 43, 44, 45, … Same as above but starts higher!
0, 6, 23,−8.2, π, e2, … Pattern Not Clear!
0.1, 0.01, 0.001, 0.0001, … Looks like it divides by 10 each time!
�
There’s nothing wrong with listing the elements of the sequence when the pat-
tern is clear. However sometimes it isn’t.
There is a formal definition, however.
Definition 1.1.1. A sequence is a function f whose domain is a set of the form
D = {n0, n0 +1, n0 +2, …} where n0 is a nonnegative integer and which outputs
real numbers. The domain is called the set of indices and n0 is the starting
index.
�
Example 1.2. If D = {3, 4, 5, 6, …} and f(n) = n2 then we get the sequence:
f(3), f(4), f(5), … = 32, 42, 52, …
�
1.2 Traditional Notation
It’s not very traditional to denote sequences the formal way and instead of f(n)
we usually write an and then simply give the starting index.
Example 1.3. The sequence above would traditionally be defined by:
an = n
2 for n ≥ 3
Then we would have a3 = 3
2 = 9, a4 = 4
2 = 16, and so on.
�
Alternately we can also use curly bracket notation.
Example 1.4. The sequence above can also be defined by:
{n2}n=3
�
The only downside to this notation is that it looks vaguely set-like. I’ll avoid it
here in the notes for this reason.
2
1.3 Recursive Sequences
Another common way to define a sequence is recursively. A recursive definition
involves giving one or more starting terms and then a formula for creating
successive terms from previous terms.
Example 1.5. We may define a sequence as follows:
a1 = 4
ak = 2ak−1 + 1 for k ≥ 2
We can then calculate each term in turn:
a2 = 2a1 + 1 = 2(4) + 1 = 9
a3 = 2a2 + 1 = 2(9) + 1 = 19
… =
…
�
We can also start by giving more than just the first term.
Example 1.6. We may define a sequence as follows:
a1 = 4
a2 = −1
ak = a
2
k−1 − ak−2 for k ≥ 3
We can then calculate each term in turn:
a3 = a
2
2 − a1 = 1− 4 = −3
a4 = a
2
3 − a2 = 9− (−1) = 10
… =
…
�
1.4 Conversion Between Definitions
In general it is hard to take a recursively defined sequence and give an an formula
for it and it is also hard to do the reverse.
However in some cases we can. There are some algebraically technical ap-
proaches to this but we just want to be able to see the pattern in some examples.
Example 1.7. The sequence ai = 3i for i ≥ 1 has terms 3, 6, 9, 12, … and can
also be defined recursively by a0 = 3 and ak = 3 + ak−1 for k ≥ 1.
�
Example 1.8. The sequence ai = 3
i for i ≥ 1 has terms 3, 9, 27, 81, … and can
also be defined recursively by a0 = 3 and ak = 3ak−1 for k ≥ 1.
�
3
1.5 Shifting Starting Indices
It may be helpful (as we will see) to shift the indices of a sequence so that it
starts at a different index.
Example 1.9. Suppose ak = k
2 for k ≥ 4. Suppose we wanted to have k ≥ 0
instead. What could we do to the ak? Well, it’s not hard to see that we would
need to have ak = (k + 4)
2 so that the first number we’re squaring is still 4
�
There is a way to be formulaic about this. Let’s assume that k is the sequence
variable.
Theorem 1.5.1. To change the starting index from a to b, replace all the k by
k + (a− b).
�
Example 1.10. Suppose ak = 5
k+k−7 for k ≥ 4. To change the starting index
to 1 we replace k by k+(4−1) = k+3 to get ak = 5k+3+(k+3)+7 = 5k+3+k+10.
�
4
2 Sums
2.1 Notation
Suppose we have a sequence an and wish to add up some finite number of terms,
for example:
We use summation notation:
Ending Index∑
n=Starting Index
an
Example 2.1. Here are some examples:
10∑
n=2
1
n
=
1
2
+
1
3
+ …+
1
10
42∑
i=3
n2 + n = (32 + 3) + (42 + 4) + …+ (422 + 42)
�
2.2 Evaluation – Just Do It!
In simple cases if we wish to evaluate a sum we can simply add up the numbers.
Example 2.2. For example:
5∑
n=2
n2 = 22 + 32 + 42 + 52 = 4 + 9 + 16 + 25 = 54
�
2.3 Special Case Formulas
We have several common sums which occur frequently:
5
n∑
k=1
1 = 1 + 1 + …+ 1 = n
n∑
k=1
n = 1 + 2 + …+ n =
n(n+ 1)
2
Gauss’ Sum
n∑
k=1
n2 = 12 + 22 + …+ n2 =
n(n+ 1)(2n+ 1)
6
Sum of Squares
n∑
k=0
rk = 1 + r + r2 + …+ rn =
1− rn+1
1− r
Geometric Sum
There are various ways to prove these but for now we’ll wait until we have
mathematical induction.
However it is worth noting that these formulas can be used to figure out more
complicated sums.
Example 2.3. Consider the sum:
50∑
k=0
3(2)4k+1
This looks a bit like the Geometric Sum but in order to use the formula we need
to do some rewriting:
50∑
k=0
3(2)4k+1 = 3
50∑
k=0
(2)4k+1
= 3
50∑
k=0
21(24)k
= 6
50∑
k=0
(16)k
= 6
(
1− 1651
1− 16
)
�
Here is a more complex example:
Example 2.4. Consider the sum:
20∑
k=2
1 + k + 5(0.3)k
6
First note we can split it up and factor out the 5:
20∑
k=2
1 +
20∑
k=2
k + 5
20∑
k=2
(0.3)k
Each of these is familiar but the starting indices are not quite right. For the
first, it’s easy to calculate anyway:
20∑
k=2
1 = 19
For the second two we can change the starting indices as long as we subtract
the parts we’re adding:
20∑
k=2
k =
[
20∑
k=1
k
]
− 1 =
20(20 + 1)
2
− 1
and:
20∑
k=2
(0.3)k =
[
20∑
k=0
(0.3)k
]
− 1− 0.3 =
1− (0.3)21
1− 0.3
− (0.3)0 − (0.3)1
All together:
20∑
k=2
1 + k + 5(0.3)k = 19 +
20(20 + 1)
2
− 1 + 5
(
1− (0.3)21
1− 0.3
− 1− 0.3
)
�
Here is a nested example:
Example 2.5. Consider the sum:
10∑
n=1
n∑
i=1
1
We evaluate this from the inside out. Parentheses may help:
10∑
n=1
[
n∑
i=1
1
]
=
10∑
n=1
[n] =
10(10 + 1)
2
�
Here is a more complicated nested example:
Example 2.6. Consider the sum:
50∑
n=5
n+1∑
i=1
i
7
We evaluate this from the inside out. Parentheses may help:
50∑
n=5
[
n+1∑
i=1
i
]
=
50∑
n=5
[
(n+ 1)(n+ 1 + 1)
2
]
=
50∑
n=5
1
2
[
n2 + 3n+ 2
]
=
1
2
[
50∑
n=5
n2 + 3
50∑
n=5
n+ 2
50∑
n=5
]
At this point we might want to do the remaining sums individually:
50∑
n=5
n2 =
[
50∑
n=1
n2
]
− 12 − 22 − 32 − 42 =
50(50 + 1)(2(50) + 1)
6
− 30
50∑
n=5
n =
[
50∑
n=1
n
]
− 1− 2− 3− 4− 5 =
50(50 + 1)
2
− 15
50∑
n=5
1 = 51
Thus together the answer is:
1
2
[
50(50 + 1)(2(50) + 1)
6
− 30 + 3
(
50(50 + 1)
2
− 15
)
+ 2(51)
]
�
2.4 Telescoping Sums
Sometimes we find that when we write out a sum almost all the terms will
cancel. These are known as telescoping sums.
Here is an example:
Example 2.7. Consider the sum:
100∑
i=1
(
1
i
−
1
i+ 1
)
If we write out a number of the terms in this sum:
100∑
i=1
(
1
i
−
1
i+ 1
)
=
(
1
1
−
1
2
)
+
(
1
2
−
1
3
)
+
(
1
3
−
1
4
)
+…+
(
1
99
−
1
100
)
+
(
1
100
−
1
101
)
We see that all but the first and last fractions cancel, leaving a result of:
1
1
−
1
101
�
8
3 Products
3.1 Notation
Suppose we have a sequence an and wish to multiply some finite number of
terms, for example:
We use product notation:
Ending Index
Π
n=Starting Index
an
Example 3.1. Here is some notation and what it means:
10
Π
n=2
1
n
=
(
1
2
)(
1
3
)
…
(
1
10
)
42
Π
i=3
n2 + n = (32 + 3)(42 + 4)…(422 + 42)
�
3.2 Evaluation – Just Do It!
In simple cases if we wish to evaluate a product we can simply multiply the
numbers.
Example 3.2. For example:
5
Π
n=2
n2 = (22)(32)(42)(52) = 14400
�
3.3 Telescoping Products
Sometimes we find that when we write out a product almost all the terms will
cancel. These are known as telescoping products.
Here is an example:
Example 3.3. Consider the product:
100
Π
i=5
i
i+ 1
If we write out a number of the terms in this sum:
100
Π
i=5
i
i+ 1
=
(
5
6
)(
6
7
)(
7
8
)
+ …+
(
99
100
)(
100
101
)
We see that most of it cancels, leaving a result of:
5
101
�
9
4 Recursively Defined Sets
4.1 Introduction
Recursive definitions may be used not just to define sequences of numbers but
to define sets.
The basic idea is that we create a set S as follows:
(a) We put some collection of things in S.
(b) We give one or more rules which say: If certain things are in S, then certain
other things must be, too.
4.2 Examples
Example 4.1. We can build a set S of all the even numbers as follows:
(a) We put the number 0 in S.
(b) Whenever a ∈ S we also put a+ 2 and a− 2 in S.
It’s fairly obvious (but can be proved!) that this set is the set of all even
numbers.
�
Example 4.2. Suppose we build a set S as follows:
(a) We put the number 1 in S.
(b) Whenever x ∈ S we also put 2x in S.
It’s fairly obvious (but can be proved!) that this set is the set of all powers of
2 greater than or equal to 1.
�
We don’t have to just build sets of numbers. Here are two examples.
Example 4.3. Suppose we build a set S as follows:
(a) We put the pair (0, 0) in S.
(b) Whenever (a, b) ∈ S we also put (a, b+1) and (a+1, b+1), and (a+2, b+1)
in S.
What else is in the set other than (0, 0)?
Well since (0, 0) ∈ S we know that (0, 1), (1, 1), (2, 1) ∈ S. But then since
(0, 1) ∈ S we know that (0, 2), (1, 2), (2, 2) ∈ S.
This goes on forever and it’s not entirely clear what is and is not in the set. For
example is (10, 10) in the set? How about (10, 20)? How about (20, 10)?
10
�
Here is one with strings.
Example 4.4. Suppose we build a set S as follows:
(a) We put the string X in S.
(b) Whenever a string s ∈ S we also put Xs and Y sY in S.
What else is in the set other than X?
Well since X ∈ S we know that XX,Y XY ∈ S. But then since Y XY ∈ S we
know that XYXY, Y Y XY Y ∈ S.
This goes on forever and it’s not entirely clear what is and is not in the set.
�
Here is a somewhat familiar example.
Example 4.5. Suppose p, q, r are the only statement variables we have. The
set S of sentences in propositional logic involving these statement variables can
be be constructed this way:
(a) We put p, q, r in S.
(b) Then:
• If X,Y ∈ S then we put (X ∧ Y ) in S.
• If X,Y ∈ S then we put (X ∨ Y ) in S.
• If X ∈ S then we put (∼X) in S.
So now we know that for example:
• p, q ∈ S so (p ∧ q) ∈ S.
• (p ∧ q) ∈ S so (∼(p ∧ q)) ∈ S.
• (∼(p ∧ q)), r ∈ S so ((∼(p ∧ q)) ∨ r) ∈ S
• Etc…
This actually then allows us to construct all statements in propositional logic
(or statements equivalent to them) using p, q, and r.
�
11
5 Binary Trees
5.1 Introduction
Binary trees are another thing which can be built recursively.
Informally a binary tree starts with a root node. The root node can then be
a parent node and connect down to either one or two child nodes. Each child
node can then connect down to either one or two more child nodes. This keeps
going until the tree ends at the leaf nodes, these are the child nodes without
children of their own.
Formally speaking one way to define a binary tree is as a specific type of graph.
Example 5.1. Here is binary tree:
�
5.2 Recursive Definition
The set of binary trees B can also be defined recursively as follows:
(a) A single node is a binary tree, so a single node is in B.
(b) If T1 and T2 are binary trees (are in B) then we can create a new binary
tree by taking a new node as the root and attaching T1 and T2 on branches
below it.
(c) If T1 is a binary tree (is in B) then we can create a new binary tree by
taking a new node as the root and attaching T1 on a branch below it.
According to this definition we get new binary trees as follows:
and are trees and therefore so is
and are trees and therefore so is
12
is a tree and therefore so is
(This last one is the first tree listed in the section.)
5.3 Properties of Binary Trees
Binary trees are heavily used in various algorithms and have several properties
which are critical to know.
We’ll just mention them here but we’ll prove some of them via structural in-
duction.
Definition 5.3.1. For a binary tree T define:
N(T ) The number of nodes in the tree.
T (E) The number of edges (connections) in the tree.
L(T ) The number of leaves in the tree.
H(T ) The height of the tree. A single node has height 0.
�
In addition:
Definition 5.3.2. A binary tree is perfect if all the notes (except the leaves)
have exactly two children and if all the leaves are at exactly the same depth.
Example 5.2. Here is a perfect tree:
Theorem 5.3.1. For a binary tree T we have:
N(T ) = E(T ) + 1
L(T ) ≤ 2H(t) With = iff T is perfect.
N(T ) ≤ 2H(t)+1 − 1 With = iff T is perfect.
Proof. See the notes on structural induction. QED
It’s worth noting that as a result of the latter two we have the following:
13
Theorem 5.3.2. For a binary tree T we have:
H(t) ≥ lgL(t) With = iff T is perfect.
H(t) ≥ lg(N(t)− 1)− 1 With = iff T is perfect.
14
Sequences
Intuition and Formal Definition
Traditional Notation
Recursive Sequences
Conversion Between Definitions
Shifting Starting Indices
Sums
Notation
Evaluation – Just Do It!
Special Case Formulas
Telescoping Sums
Products
Notation
Evaluation – Just Do It!
Telescoping Products
Recursively Defined Sets
Introduction
Examples
Binary Trees
Introduction
Recursive Definition
Properties of Binary Trees