Chapter 5.1 - Help-A-Bull

Report
Discrete Mathematics and Applications
Chapter 5: Sequences, Mathematical
Induction and Recursion
5.1 Sequences
Yan Zhang ([email protected])
Department of Computer Science and Engineering, USF
Sequences
• A sequence is a function.
• Function  ∶  → 
– Every element  in  is mapped to only one element  in , such
that (, ) ∈ .
Domain: A
∶  → 
Codomain: B
Not allowed
2
Sequences
Definition
• A sequence is a function.
• Domain is either all the integers between two given integers or all the integers
greater than or equal to a given integer.
Finite sequences:  , +1 , +2 , ⋯ , 
Domain

+1
+2
⋯

Codomain

+1
+2
⋯

Infinite sequences:  , +1 , +2 , ⋯
Domain

+1
+2
⋯
Codomain

+1
+2
⋯
 (read “ sub ”) is called a term.
 in  is called a subscript or index.
Initial term: 
Final term: 
3
Sequence Example 1
Finding Terms of Sequences Given by Explicit Formulas
Define sequences 1, 2, 3, … and 2, 3, 4, … by the following
explicit formulas:
Compute the first five terms of both sequences.
Solution:
1 =
2 =
1
1+1
2−1
2
1
2
1
,
2
2
2
= ,
2+1
3
3−1
2
= ,
3
3
3
3
= ,
3+1
4
4−1
3
= ,
4
4
= , 2 =
3 =
4 =
=
4 =
5 =
3 =
4
4
= ,
4+1
5
5−1
4
= ,
5
5
5 =
6 =
5
5
=
5+1
6
6−1
5
=
6
6
Note: all terms of both sequences are identical.
4
Sequence Example 2
Finding an Explicit Formulas to Fit Given Initial Terms
Find an explicit formula for a sequence that has the following
initial terms:
1 1
1 1
1
1, − , , − , , − , ⋯
4 9 16 25 36
Solution:
• Denote the general term of the sequence by  and suppose
the first term is 1 .
1 =
1
,
12
2 = (−1)
1
,
22
3 =
1
,
32
4 = (−1)
1
,
42
5 =
1
,
52 6
= (−1)
1
62
• An explicit formulator that gives the correct first six terms is:
1
+1
 = (−1)
2
5
Summation Notation
Given a sequence  , +1 , +2 , ⋯ ,  ,
Domain

+1
+2
⋯

Codomain

+1
+2
⋯

The summation from  equals  to  of -sub-:

= 
=  + +1 + ⋯ +
Summation notation
Expanded form
: the index of the summation
: the lower limit of the summation
: the upper limit of the summation
6
Summation Example
– Computing Summations
Let 1 = −2, 2 = −1, 3 = 0, 4 = 1, and 5 = 2.
Compute the following:
a.
5
=1 
5
 = 1 + 2 + 3 + 4 + 5 = −2 + −1 + 0 + 1 + 2 = 0
=1
b.
c.
2
=2 
2
=2  = 2
= −1
2
=1 2
2
=1 2
= 2 + 4 = −1 + 1 = 0
7
Summation Example
– Changing from Summation Notation to Expanded Form
Write the following summation in expanded form:
Solution:
8
Summation Example
– Changing from Expanded Form to Summation Notation
Express the following using summation notation:
Solution:
The general term of this summation can be expressed as
for integers k from 0 to n.
Hence
9
Summation Notation - Recursive Definition
If  is any integer and  < , then

 = 
=
+1

 =
 + +1
=
=
+2
+1
 =
=

 + +2
=
⋯
−1
 =
=
 + 
=
Recursive definition is useful to rewrite a summation,
– by separating off the final term of a summation
– by adding a final term to a summation.
10
Recursive Definition Example
– Separating Off a Final Term and Adding On a Final Term
a. Rewrite
b. Write
by separating off the final term.
as a single summation.
Solution:
a.
b.
11
Summation Notation - A Telescoping Sum
• In certain sums each term is a difference of two
quantities.
For example:  =
1

1
−
,
+1
= , ⋯ , 
• When you write such sums in expanded form, you
sometimes see that all the terms cancel except the
first and the last.
 + +1 + +2
1
1
1
1
1
1
=
−
+
−
+
−
 +1
+1 +2
+2 +3
• Successive cancellation of terms collapses the sum
like a telescope.
12
A Telescoping Sum Example
Some sums can be transformed into telescoping sums,
which then can be rewritten as a simple expression.
For instance, observe that
Use this identity to find a simple expression for
13
Product Notation
Given a sequence  , +1 , +2 , ⋯ ,  ,
Domain

+1
+2
⋯

Codomain

+1
+2
⋯

The product from  equals  to  of -sub-:

= 
=  ∙ +1 ∙ ⋯ ∙ 
A recursive definition for the product notation is the following:
If  is any integer, then
14
Product Notation Example
– Computing Products
Compute the following products:
a.
b.
Solution:
a.
b.
15
Properties of Summations and Products
16
Properties of Summation & Product Exercise
Let  =  + 1 and  =  − 1 for all integers . Write
each of the following expressions as a single summation or
product:
a.
b.
17
Properties of Summation & Product Exercise
Solution:
a.
18
Properties of Summation & Product Exercise
Solution:
b.
19
Change of Variable
• The index symbol in a summation or product is internal
to summation or product.
• The index symbol can be replaced by any other symbol
as long as the replacement is made in each location
where the symbol occurs.

= 
=

= 
and

= 
=

= 
• As a consequence, the index of a summation or a
product is called a dummy variable.
• A dummy variable is a symbol that derives its entire
meaning from its local context. Outside of that context,
the symbol may have another meaning entirely.
20
Change of Variable Exercise 1
summation:
change of variable:
21
Change of Variable Exercise 1 - Solution
Solution:
• First calculate the lower and upper limits of the new
summation:
Thus the new sum goes from j = 1 to j = 7.
• Next calculate the general term of the new summation by
replacing each occurrence of k by an expression in j :
• Finally, put the steps together to obtain
22
Factorial Notation
A recursive definition for factorial is the following: Given
any nonnegative integer ,
23
Factorials Exercise
Simplify the following expressions:
a.
b.
c.
d.
Solution:
a.
e.
d.
e.
b.
24
Factorials Exercise Solution
c.
25
“n Choose r ” Notation
Chose 2 objects from {a,b,c,d}:
{a, b}, {a, c}, {a, d}, {b, c}, {b,d}, and {c, d}.
26
“n Choose r” Exercise
Use the formula for computing
expressions:
a.
b.
to evaluate the following
c.
Solution:
a.
27
“n Choose r” Exercise
b.
c.
28
n Choose r Properties
•
•
•
•
•



0






=
=
=
=
=

for 0 ≤  ≤ 
−

=1


−+1
for  > 0

−1
−1 
for  < 
−

−1 
for ,  > 0
−1 
29
Exercise
Prove that for all nonnegative integers  and  with  + 1 ≤ ,

− 
=
.
+1 
+1
30
Exercise
Prove that for all nonnegative integers  and  with  + 1 ≤ ,

− 
=
.
+1 
+1
Hint:
− 
−
!
=
∙

+1
 + 1 !  −  !
=
−
+1
=
!
(+1)! −−1 !
∙
!
! − ∙ −−1 !

=
+1
31

similar documents