# discrete mathematics & mathematical reasoning sequences ... discrete mathematics &...

Post on 24-Jun-2020

1 views

Embed Size (px)

TRANSCRIPT

Discrete Mathematics & Mathematical Reasoning Sequences and Sums

Colin Stirling

Informatics

Slides based on ones by Myrto Arapinis

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 1 / 14

Sequences

Sequences are ordered lists of elements

2, 3, 5, 7, 11, 13, 17, 19, . . . or a, b, c, d , . . ., y , z

Definition A sequence over a set S is a function f from a subset of the integers (typically N or Z+) to the set S. If the domain of f is finite then the sequence is finite

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 2 / 14

Sequences

Sequences are ordered lists of elements

2, 3, 5, 7, 11, 13, 17, 19, . . . or a, b, c, d , . . ., y , z

Definition A sequence over a set S is a function f from a subset of the integers (typically N or Z+) to the set S. If the domain of f is finite then the sequence is finite

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 2 / 14

Examples

f : Z+ → Q is f (n) = 1/n defines the sequence

1, 1/2, 1/3, 1/4, . . .

Assuming an = f (n), the sequence is also written a1, a2, a3, . . .

or as {an}n∈Z+

g : N→ N is g(n) = n2 defines the sequence

0, 1, 4, 9, . . .

Assuming bn = g(n), also written b0, b1, b2, . . .

or as {bn}n∈N

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 3 / 14

Examples

f : Z+ → Q is f (n) = 1/n defines the sequence

1, 1/2, 1/3, 1/4, . . .

Assuming an = f (n), the sequence is also written a1, a2, a3, . . .

or as {an}n∈Z+

g : N→ N is g(n) = n2 defines the sequence

0, 1, 4, 9, . . .

Assuming bn = g(n), also written b0, b1, b2, . . .

or as {bn}n∈N

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 3 / 14

Examples

f : Z+ → Q is f (n) = 1/n defines the sequence

1, 1/2, 1/3, 1/4, . . .

Assuming an = f (n), the sequence is also written a1, a2, a3, . . .

or as {an}n∈Z+

g : N→ N is g(n) = n2 defines the sequence

0, 1, 4, 9, . . .

Assuming bn = g(n), also written b0, b1, b2, . . .

or as {bn}n∈N

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 3 / 14

Examples

f : Z+ → Q is f (n) = 1/n defines the sequence

1, 1/2, 1/3, 1/4, . . .

Assuming an = f (n), the sequence is also written a1, a2, a3, . . .

or as {an}n∈Z+

g : N→ N is g(n) = n2 defines the sequence

0, 1, 4, 9, . . .

Assuming bn = g(n), also written b0, b1, b2, . . .

or as {bn}n∈N

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 3 / 14

Examples

f : Z+ → Q is f (n) = 1/n defines the sequence

1, 1/2, 1/3, 1/4, . . .

Assuming an = f (n), the sequence is also written a1, a2, a3, . . .

or as {an}n∈Z+

g : N→ N is g(n) = n2 defines the sequence

0, 1, 4, 9, . . .

Assuming bn = g(n), also written b0, b1, b2, . . .

or as {bn}n∈N

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 3 / 14

Geometric and arithmetic progressions

A geometric progression is a sequence of the form

a, ar , ar2, ar3, . . . , arn, . . .

Example {bn}n∈N with bn = (−1)n

An arithmetic progression is a sequence of the form

a, a + d , a + 2d , a + 3d , . . . , a + nd , . . .

Example {cn}n∈N with cn = 7− 3n

where the initial elements a, the common ratio r and the common difference d are real numbers

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 4 / 14

Geometric and arithmetic progressions

A geometric progression is a sequence of the form

a, ar , ar2, ar3, . . . , arn, . . .

Example {bn}n∈N with bn = (−1)n

An arithmetic progression is a sequence of the form

a, a + d , a + 2d , a + 3d , . . . , a + nd , . . .

Example {cn}n∈N with cn = 7− 3n

where the initial elements a, the common ratio r and the common difference d are real numbers

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 4 / 14

Geometric and arithmetic progressions

A geometric progression is a sequence of the form

a, ar , ar2, ar3, . . . , arn, . . .

Example {bn}n∈N with bn = (−1)n

An arithmetic progression is a sequence of the form

a, a + d , a + 2d , a + 3d , . . . , a + nd , . . .

Example {cn}n∈N with cn = 7− 3n

where the initial elements a, the common ratio r and the common difference d are real numbers

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 4 / 14

Geometric and arithmetic progressions

A geometric progression is a sequence of the form

a, ar , ar2, ar3, . . . , arn, . . .

Example {bn}n∈N with bn = (−1)n

An arithmetic progression is a sequence of the form

a, a + d , a + 2d , a + 3d , . . . , a + nd , . . .

Example {cn}n∈N with cn = 7− 3n

where the initial elements a, the common ratio r and the common difference d are real numbers

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 4 / 14

Geometric and arithmetic progressions

A geometric progression is a sequence of the form

a, ar , ar2, ar3, . . . , arn, . . .

Example {bn}n∈N with bn = (−1)n

An arithmetic progression is a sequence of the form

a, a + d , a + 2d , a + 3d , . . . , a + nd , . . .

Example {cn}n∈N with cn = 7− 3n

where the initial elements a, the common ratio r and the common difference d are real numbers

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 4 / 14

Recurrence relations

Definition A recurrence relation for {an}n∈N is an equation that expresses an in terms of one or more of the elements a0, a1, . . . , an−1

Typically the recurrence relation expresses an in terms of just a fixed number of previous elements (such as an = g(an−1, an−2)) The initial conditions specify the first elements of the sequence, before the recurrence relation applies A sequence is called a solution of a recurrence relation iff its terms satisfy the recurrence relation

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 5 / 14

Recurrence relations

Definition A recurrence relation for {an}n∈N is an equation that expresses an in terms of one or more of the elements a0, a1, . . . , an−1

Typically the recurrence relation expresses an in terms of just a fixed number of previous elements (such as an = g(an−1, an−2))

The initial conditions specify the first elements of the sequence, before the recurrence relation applies A sequence is called a solution of a recurrence relation iff its terms satisfy the recurrence relation

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 5 / 14

Recurrence relations

Definition A recurrence relation for {an}n∈N is an equation that expresses an in terms of one or more of the elements a0, a1, . . . , an−1

Typically the recurrence relation expresses an in terms of just a fixed number of previous elements (such as an = g(an−1, an−2)) The initial conditions specify the first elements of the sequence, before the recurrence relation applies

A sequence is called a solution of a recurrence relation iff its terms satisfy the recurrence relation

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 5 / 14

Recurrence relations

Typically the recurrence relation expresses an in terms of just a fixed number of previous elements (such as an = g(an−1, an−2)) The initial conditions specify the first elements of the sequence, before the recurrence relation applies A sequence is called a solution of a recurrence relation iff its terms satisfy the recurrence relation

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 5 / 14

Rabbits and Fibonacci sequence

A young pair of rabbits (one of each sex) is placed on an island

A pair of rabbits does not breed until they are 2 months old. After they are 2 months old each pair produces another pair each month

Find a recurrence relation for number of rabbits after n months assuming no rabbits die

Answer is the Fibonacci sequence f (0) = 0 f (1) = 1 f (n) = f (n − 1) + f (n − 2) for n ≥ 2

Yields the sequence 0, 1, 1, 2, 3, 5, 8, 13, . . .

Colin Stirling (Informatics) Discrete Mathematics (Section 2.4) Today 6 / 14

Rabbits and Fibonacci sequence

A young pair of rabbits (one of each sex) is placed on an island

A pair of rabbits does not breed until they are 2 months old. After they are 2 months old each pair produces another pair each month

Find a recurrence relation for number of rabbits after n months assuming no rabbits die

Answer is the Fibonacci sequence f (0) = 0 f (1) = 1 f (n) = f (n − 1) + f (n − 2) for n ≥ 2

Yields the sequence 0, 1, 1, 2, 3, 5, 8, 13, . . .

Colin Sti