Transcript chapter 8 - James Bac Dang

CHAPTER 10
Sequences, Induction, &
Probability
10.1 Sequences & Summation
Notation
• Objectives
– Find particular terms of sequence from the
general term
– Use recursion formulas
– Use factorial notation
– Use summation notation
What is a sequence?
• An infinite sequence is a function whose domain
is the set of positive integers. The function
values, terms, of the sequences are represented
by a , a , a ,...a ...
1
2
3
n
• Sequences whose domains are the first n
integers, not ALL positive integers, are finite
sequences.
Recursive Sequences
• A specific term is given.
• Other terms are determined based on the value of
the previous term(s)
• Example: a3  10, an1  3  an  1, find : a1 , a2 , a4
•
a3  10  3a2  1
10  1
a2 
 3  3a1  1
3
3 1 2
a1 

3
3
a4  3a3  1  3(10)  1  31
Find the 1st 3 terms of the sequence:
n 1
an 
n!
•
•
•
•
1)4, 5/2, 6
2)4, 5/2, 1
3)1, 2, 3
4)4, 5, 6
Summation Notation
• The sum of the first n terms, as i goes from 1 to n
n
is given as:
a a  a  a  ...  a  a

i 1
i
1
2
3
n 1
n
• Example:
8
 5i  2  [(5  4)  2]  [(5  5)  2]  [(5  6)  2]  [(5  7)  2]  [(5  8)  2]
i 4
 18  23  28  33  102
10.2 Arithmetic Sequences
• Objectives
– Find the common difference for an arithmetic
sequence
– Write terms of an arithmetic sequence
– Use the formula for the general term of an
arithmetic sequence
– Use the formula for the sum of the first n
terms of an arithmetic sequence
What is an arithmetic
sequence?
• A sequence where there is a common
difference between every 2 terms.
• Example: 5,8,11,14,17,…..
• The common difference (d) is 3
• If a specific term is known and the difference
is known, you can determine the value of any
term in the sequence
• For the previous example, find the 20th term
• (continue on next slide)
Example continued
• The first term is 5 and d=3
• Notice between the 1st & 2nd terms there is 1
(3). Between the 1st & 4th terms there are 3
(3’s). Between the 1st & nth terms there would
be (n-1) 3’s
• 20th term would be the 1st term + 19(3’s)
a20  5  19(3)  62
The sum of the 1st n terms of an
arithmetic sequence
• Since every term is increasing by a constant
(d), the sequence, if plotted on a graph (x=the
indicated term, y=the value of that term),
would be a line with slope= d
• The average of the 1st & last terms would be
greater than the 1st term by k and less than
the last term by k. The same is true for the 2nd
term & the 2nd to last term, etc
• Therefore, you can find the sum by replacing
each term by the average of the 1st & last
terms (continue next slide)
Sum of an arithmetic sequence
• If there are n terms in the arithmetic
sequence and you replace all of them with
the average of the 1st & last, the result is:
 a1  an 
Sn  n  

 2 
Find the sum of the 1st 30 terms of
the arithmetic sequence if
a1  6, d  6
•
•
•
•
1) 81
2) 3430
3) 2430
4) 168
10.3 Geometric Sequences &
Series
• Objectives
– Find the common ratio of a geometric sequence
– Write terms of a geometric sequence
– Use the formula for the general term of a geometric
sequence
– Use the formula for the sum of the 1st n terms of a
geometric sequence
– Find the value of an annuity
– Use the formula for the sum of an infinite geometric
series
What is a geometric sequence?
• A sequence of terms that have a common
multiplier (r) between all terms
• The multiplier is the ratio between the
(n+1)th term & the nth term
• Example: -2,4,-8,16,-32,…
• The ratio between any 2 terms is (-2)
which is the value you multiply any term by
to find the next term
•
•
•
•
•
Given a term in a geometric
sequence, find a specified other
term
st
th
Example: If 1 term=3 and r=4, find the 14 term
Notice to find the 2nd term, you multiply 3(4)
To find the 3rd term, you would multiply 3(4)(4)
To find the 4th term, multiply 3(4)(4)(4)
To find the nth term, multiply: 3(4)(4)(4)…
(n-1 times)
13
th
• 14 term = 3(4)  201,326,592
• (in a geometric sequence, terms get large quickly!)
Sum of the 1st n terms of a
geometric sequence
a1 (1  r )
Sn 
1 r
n
What if 0<r<1 or -1<r<0?
• Examine an example:
• If 1st term=6 and r=-1/3
2 2 2 2 2
6,2, ,
, ,
,
,...
3 9 27 81 243
• Even though the terms are alternating between
pos. & neg., their magnitude is getting smaller &
smaller
• Imagine infinitely many of these terms: the terms
become infinitely small
Find the Sum of an Infinite
Geometric Series
• If -1<r<1 and r not equal zero, then we CAN find
the sum, even with infinitely many terms
(remember, after a while the terms become
infinitely small, thus we can find the sum!)
 a1 (1  r n ) 

S n  
• If
 1  r  and n is getting very large, then r
raised to the n, recall, is getting very, very
small…so small it approaches zero, which allows
us to replace r raised to the nth power with a zero!
• This leads to: S  a1
n
1 r
Repeating decimals can be
considered as infinite sums
•
•
•
•
•
Example: Write .34444444…as an infinite sum
Separate the .3 from the rest of the number:
.3444….. = .3 + .044444…..
.044444….. = .04 + .004 + .0004 + .0004+…
This is an infinite sum with 1st term=.04,r=.1
.04 .04 4
2
S 



1  .1 .9 90 45
3
2 27 4 31




• .3444….=
10 45 90 90 90
10.4 Mathematical Induction
• Objectives
– Understand the principle of mathematical
induction
– Prove statements using mathematical
induction
What is mathematical induction?
• A method of proof. To prove something holds
true for all values of n, you cannot simply plug
in numbers. Why not? Because you could
never verify something is true for ALL numbers.
• Using this method, you prove a statement is
true for one term (generally the 1st) and then if
you assume the statement is true for the kth
term, you must prove it holds true for the
(k+1)th term.
• If you can prove it is true for the (k+1)th term, it
must be true for all terms.
Carefully examine examples in
the book for mathematical
induction.
10.5 The Binomial Theorem
• Objectives
– Evaluate a binomial coefficient
– Expand a binomial raised to a power
– Find a particular term in a binomial
expansion
What is the binomial theorem?
• The binomial theorem provides a means to expand a
binomial expression.
• It provides a “shortcut” to taking an expression, such
as (a+b) and raising it to a power (n) without having
to continue to multiply binomials out.
 n  n  n  n 1  n  n 2 2
 n n
(a  b)   a   a b   a b  ...   b
0
1 
 2
 n
n
What is
 n ?
 
r 
• This is the binomial coefficient in the previous
expansion of binomials
• It may also be considered as the combination
of n objects taken r at a time.
 n
n!
  
 r  r!(n  r )!
Use binomial expansion theorem to
find
(3a  2b)
6
 6
 6
 6
 6
6
5
1
4
2
 (3a )   (3a ) (2b)   (3a ) (2b)   (3a ) 3 (2b) 3 
 0
1 
 2
3
6
 6
 6
2
4
1
5
 (3a ) (2b)   (3a ) (2b)    (2b) 6
 4
5
 6
 729a 6  2916a 5b  4860a 4b 2  4320a 3b 3  2160a 2b 4  576ab 5  64b 6
10.6 Counting Principles,
Permutations, & Combinations
• Objectives
– Use the fundamental counting principle
– Use the permutations formula
– Distinguish between permutation
problems & combination problems
– Use the combinations formula
What is the Fundamental Counting
Principle?
• It is the notion that if one event can
happen in “a” different ways and another
event can occur in “b” different ways, then
there are “a times b” different ways for
BOTH events to happen together.
• Example: If you have 5 shirts and 3 pair of
jeans, there are 15 different outfits
comprised of a shirt & a pair of jeans.
What is a permutation?
• An ordered arrangement of items.
• For example, if you have a telephone
number comprised of 10 different digits,
the order matters. Two people could have
DIFFERENT phone numbers made up of
the same digits.
• 402-555-2378 is NOT 402-555-3287
• There are 2 permutations of that set of 10
digits.
How many different permutations of
n objects are there?
• There are n choices for the 1st object, (n-1)
choices for the 2nd object, (n-2) choices for
the 3rd object, etc, until there is only 1
choice for the last object.
• Since we want all these choices to happen
at the same time, we apply Fundamental
Counting Principle and multiply the #
choices:
• n(n-1)(n-2)(n-3)(n-4)…(2)(1)
What if you want to look at the
different ordered arrangements of
any 4 non-repeated letters of the
alphabet for a password?
• There are 26 different objects (letters) and
we’re taking just 4 of them at a time.
• There are 26 choices for the 1st letter, 25
for the 2nd letter, 24 for the 3rd letter and 23
choices for the 4th letter.
• Thus there are 26(25)(24)(23)=358,800
different passwords.
Would it have made a difference if
the letters could be repeated?
• Yes, then there would be 26 choices for
the 1st letter, 26 choices for the 2nd letter,
26 choices for the 3rd letter and 26 choices
for the 4th letter.
• Total=456,976 different passwords with
letters possibly repeated.
Permutations of n objects taken r at
a time (none repeated)
• General formula
 n
n!
  
r
  (n  r )!
What if we don’t care about order?
• There are 25 children in a class and I’m
selecting 4 of them to clean the board. Does it
matter if I select Joe, Mary, Sue & Tim or Sue,
Joe, Mary & Tim? NO – it is exactly the same
result.
• The number of ways to select n objects r at a
time, when order DOES NOT matter, is
considered the COMBINATION of n objects
taken r at a time.
10.7 Probability
• Objectives
– Compute empirical probability
– Compute theoretical probability
– Find the probability that an event will not occur
– Find the probability of one event or a second
event occurring
– Find the probability of one event & a second
event occurring.
If order does NOT matter, we must
divide out the ways that are the
same.
• How many different ways are there to arrange
any “r” objects? There are r! ways.
• Therefore, the combination of n objects taken r
at a time is:
n!
n Cr 
(n  r )! r!
What is probability?
• Probability of an
event happening =
# successes
total# outcomes
Empirical probability
• We COUNT or OBSERVE outcomes.
• Often referred to as experimental
probability.
• An experiment is done, or situation exists,
and various outcomes are recorded.
• The empirical (experimental) probability is
the ratio of total number of successful
outcomes (however it has been defined) to
the total number of outcomes.
Theoretical Probability
• An actual experiment is rather conducted.
Successful outcomes are determined based on
known information regarding the event.
• For example, if one has a fair die and there are
6 sides to the die, the probability of rolling a 4 is
1/6.
• We don’t roll the die to count outcomes, rather
we are assured the die is fair, thus there is 1
success (a “4” in this example) and 6 possible
outcomes (1,2,3,4,5, or 6), the theoretical
probability of rolling a 4 is 1/6.
What is the probability of selecting
3 men & 2 women for a committee
from a room of 10 men & 15
women?
• Success = select 3 men & 2 women (order does
NOT matter) (use combinations for # ways to
select 3 men & for selecting 2 women, THEN
apply Fundamental Counting Principle)
10
C3 15 C2  120 105  12,600
• Total outcomes = select any 5 of the 15 people
25
C5  53,130
• Probability = .24 (approx.)
Independent Events
• If the outcome of one event does NOT
effect the outcome of the other event they
are considered to be independent.
Mutually Exclusive Events
• 2 events that canNOT happen at the same
time
If you know the probability of an
event occurring, what is the
probability it will NOT occur?
• Total probability of all options of any event
occurring must equal 1.
• Therefore, if P(A)=x, P(not A) = 1 – x
• If the probability of rain on a given day is
30%, the probability it will NOT rain is 70%