Chapter 7
Advanced Counting Techniques

 Modified: 

© Ray Wisman

Resources

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/index.html - Index to the Rosen text Web site learning resources.

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter7/self_assessments.html - Chapter self-assessment with answers and explanations .

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter7/extra_examples.html - Extra examples with solutions.

Sequences

Definition

Sequence is a discrete structure used to represent an ordered list.

Example

1, 3, 5, 7, 11 is ordered sequence of 5 terms

1, 3, 5, 7, 11, ... is an infinite sequence

Definition 1

Sequence is a function from a subset of the set of integers, usually {0, 1, 2, ...} or {1, 2, 3, ...}, to a set S.

an, a sequence term, denotes the image of the integer n.

f(n) = an

{an} describes the sequence.

Example

Sequence {an}

an = 1/n

List of terms starts at n=1

a1, a2, a3, a4, a5, ...
1/1, 1/2, 1/3, 1/4, 1/5, ...

Question 7.0.1 In the above sequence, what is:

  1. a6 =
  2. a42 =

Recurrence Relations

The recursive n! algorithm of:

int factorial (int n) {

   if (n == 1) return 1;

   return factorial (n-1) * n;
}

has a running time, an, defined as recurrence:

a1 = 1

an = an-1 + 1        ∀n > 1

where 1 is the running time for each execution of the factorial function.

The recurrence has a closed form solution:

an = n                      ∀n ≥ 1

The running time to calculate 100! is then:

a100 = 100              ∀n ≥ 1

Question 7.0.2

a57 = ?

 

7.1 Recurrence Relations

Definition 1

Recurrence relation expresses the sequence {an} as one or more previous terms: a0, a1, a2, ..., an-1

for all integers n≥n0 and n0 is a nonnegative integer.

Example 1

{an} a sequence satisfying:

an = an-1 - an-2

a0 = 3

a1 = 5

What are a2 and a3?

a2 = a2-1 - a2-2 = a1 - a0 = 5 - 3 = 2

a3 = a3-1 - a3-2 = a2 - a1 = 2 - 5 = -3

Definition

Initial conditions specify the terms that precede the first term where the recurrence relation takes effect.

Example

{an} a sequence satisfying:

an = an-1 - an-2

Initial conditions

a0 = 3

a1 = 5

a2 = a1 - a0 = 5 - 3 = 2

Question 7.1

{an} a sequence with the closed form solution:

an = 2n

What are a0, a1 and a2?

Question 7.2

{an} a sequence satisfying:

an = an-1 + an-2

a0 = 3

a1 = 5

What are a2, a3 and a4?

 

Definition

Solution is a closed form equal to a recurrence relation.

Example 2

Determine whether {an}

 an = 5

is a solution of the recurrence relation:

a0 = 5
a1 = 5
an = 2an-1 - an-2                     for n=2, 3, 4 ...

For example:

a2 = 2a1 - a0 = 2*5 - 5 = 5

Assume (already shown for a0, a1and a2)

an-1 = 5
an-2 = 5

Proof      an = 2an-1 - an-2 = 5

an = 2an-1 - an-2 Recurrence
  = 2(5) - 5 Substitution
    an-1 = 5
    an-2 = 5
  = 10 - 5 Multiply
∴ = 5 Simplify

Question 7.3.0

Determine whether {an}

an = 4

is a solution of the recurrence relation:

a0 = 4
a1 = 4
an = 3an-1 - 2an-2                     for n=2, 3, 4, ...

Assume:

an-1 = 4
an-2 = 4

Proof     

an = 3an-1 - 2an-2 = 4

an = 3an-1 - an-2 Recurrence
  = Substitution
    an-1 = 4
    an-2 = 4
  =  Multiply
∴ = 4 Simplify

 

Example 3

Determine whether {an}

an = 2n

is a solution of the recurrence relation:

an = 2an-1 - an-2                    for n=2, 3, 4 ...

Proof

an = 2n = 2an-1 - an-2

Not a solution by finding a2 both ways

a0 = 20 = 1
a1 = 21 = 2

a2

22 = 4 ≠ 2a1 - a0 = 2*2 - 1 = 3

2n ≠2an-1 - an-2

 

Question 7.3.1

Determine whether {an}

an = 2n

is a solution of the recurrence relation:

a0 = 0
a1 = 2
an = 3an-1 - an-2                     for n=0, 1, 2, ...

Show     

an = 3an-1 - an-2 = 2n

What is: n=2

 

Proof:    Assume

     an-1 = 2(n-1)
     an-2 = 2(n-2)
an = 3an-1 - an-2 Recurrence
  = 3(2(n-1)) - 2(n-2) Substitution
     an-1 = 3(n-1)
     an-2 = 3(n-2)
  = 3( 2n - 2) - 2n + 4 Multiply
  = 6n - 6 - 2n + 4 Multiply
  = 4n - 2 Simplify
  ≠ 2n Fails

 

Example 4

Determine whether {an}

where an = 3n

is a solution of the recurrence relation:

an = 2an-1 - an-2                     for n=2, 3, 4, ...

Example:

an = 3n                            Closed solution

a0 = 3*0 = 0
a1 = 3*1 = 3

a2 = 3*2 = 6 = 2a1 - a0 = 2*3 = 6
a3 = 3*3 = 9 = 2a2 - a1 = 2*6 - 3 = 9

Proof        an = 2an-1 - an-2 = 3n

an = 2an-1 - an-2 Recurrence
  = 2(3(n-1)) - 3(n-2) Substitution
     an-1 = 3(n-1)
     an-2 = 3(n-2)
  = 2( 3n - 3) - 3n + 6 Multiply
  = 6n - 6 - 3n + 6 Multiply
∴ = 3n Simplify

Question 7.4

Determine whether {an}

an = 2n

is a solution of the recurrence relation:

an = 2an-1 - an-2             for n=2, 3, 4, ...

What are:

a0 =
a1 =

an-1 =
an-2 =

Proof    an = 2an-1 - an-2 = 2n

an = 2an-1 - an-2 Recurrence
  = Substitution
     an-1 =           
     an-2 =
  =  Multiply
  = Multiply
∴ = 2n Simplify

 

Finding a Closed Form solution using an Iterative Approach

  1. Start with the recurrence relation
  2. Use substitution to write an in terms of an-1, an-1 in terms of an-2, an-1 in terms of an-2 and so forth.
  3. When reaching the end, use the given initial value of a0
  4. Gives closed formula or a finite series, which can sum to obtain closed formula.

 

Question 7.5.1

Recurrence

an =  3an-1

a0 = 2

Closed form

an = 3n*2

Using both recurrence and closed form, what is:

a1 = 

a2 = 

 

Example - Similar to Section 7.1, Question 9

an =  3an-1

a0 = 2

What are:     an-1 = ?      an-2 = ? 

Find closed form

an = 3an-1     an-1 = 3an-2
  = 3(3an-2)    

Substitute

  = 32an-2    

an-2 = 3an-3

  = 32(3an-3)    

Substitute

  = 33an-3      
        :    

Observe pattern
  = 3nan-n    

Simplify
  = 3na0      
  = 3n*2     Initial value

Question 7.5.2

an =  2an-1

a0 = 5

What is:

an-4 = 

Find closed form

an = 2an-1     an-1 = 2an-2
  =    

Substitute

  =    

an-2 = 2an-3

  =                      

Substitute

  =      
        :    

Observe pattern
  =    

Simplify
  =      
  =     Initial value a0 = 5

Question 7.6.1

Recurrence

an =  an-1+2

a0 = 3

Closed form

an = 3+2n

Using both recurrence and closed form, what is:

a1 = 

a2 = 

Example

an = an-1+2

a0 = 3

Find closed form

an = an-1+2   an-1 = an-2+2
  = (an-2+2)+2   Substitute
  = (an-3+2)+2+2   an-2 = an-3+2
  = an-3+2*3   Substitute
           :   Observe pattern
  = an-n+2*n    
  = a0+2n    
  = 3+2n   Initial value

Question 7.6.2

an = an-1 + 4

a0 = 2

What are:     an-1 = ?      an-2 = ?

Find the closed form solution.

an = an-1 + 4   an-1 = an-2 + 4
  =     Substitute
  =   an-2 =
  =                           Substitute
           :   Observe pattern
  =     
  =    
  =   Initial value a0 = 2

 

Example

Proof by induction that:

an+1 = a0 + 2(n+1)

Recurrence

an = an-1 + 2

Base

a0 is initial value, a given truth in this case.

Induction Hypothesis

an = a0 + 2n

Prove

an+1 = a0 + 2(n+1)

a(n+1) = a(n+1)-1 + 2 By recurrence: an = an-1+2
= an + 2  
= (a0 + 2n) + 2 Substitution of Induction Hypothesis
= a0 + 2(n+1)  

Example

an =  -3an-1

a0 = 2

Find closed form

an = -3an-1   an-1 =  -3an-2
  = -3(-3an-2)    
  = -32an-2   an-2 =  -3an-3
  = -32(-3an-3)    
  = -33an-3    
        :    
  = -3na0    
  = -3n*2    

Example

an =  nan-1

a0 = 5

an = nan-1   an-1 = (n-1)an-2
  = n(n-1)an-2    
  = n(n-1)(n-2)an-3   an-2 = (n-2)an-3
        :    
  = n!a0    
  = 5n!    

Example

an = n + an-1

a0 = 2

an = n + an-1   an-1 = (n-1) + an-2
  = n + [ (n-1) + an-2 ]    
  = (n + (n-1)) + an-2    
                    :    
  = n + (n-1) + (n-2) + ... + 2 + 1 + an-n    
  = n + (n-1) + (n-2) + ... + 2 + 1 + a0   Recall that:
  = n(n+1) + 2
       2		   1+2+3+...+n = n(n+1)
                               2

Modeling with Recurrence Relations

Example - Compound Interest

11% interest compounded annually

P0 = $10,000

P1 = P0 + 0.11P0 = 1.11P0

P2 = P1 + 0.11P1 = 1.11P1 

P3 = P2 + 0.11P2 = 1.11P2 

Recurrence relation

Pn = Pn-1 + 0.11Pn-1 = 1.11Pn-1

Find closed form of Pn

Pn = 1.11Pn-1 Recurrence
  =  1.11(1.11Pn-2)  Substitute
     Pn-1= 1.11Pn-2
  = 1.11(1.11(1.11Pn-3))  Substitute
     Pn-2= 1.11Pn-3
               : Observe pattern
  = 1.11nPn-n  
  = 1.11nP0  

Pn = 1.11nP0

Amount in 30 years?

Initial conditions

P0 = $10,000

P30 = 1.1130 * $10,000 = $228,922.97

 

Proof by induction that:

Pn+1 = 1.11n+1P0

Base

P0 is initial value, a given truth in this case.

Induction Hypothesis

Pn = 1.11nP0

Prove

Pn+1 = 1.11n+1P0

P(n)+1 = 1.11P(n-1)+1 By recurrence definition: Pn = 1.11Pn-1
  = 1.11Pn  
  = 1.11(1.11nP0) Substitution of IH: Pn = 1.11nP0
  = 1.11n+1P0  

Question 7.7

3% interest compounded annually

P0 = $1,000

P1 = P0 + 0.03P0 = 1.03P0

P2 = ?

P3 = ?

Recurrence relation

Pn = ?

Find closed form of Pn

Pn =    Recurrence
  =   Substitute
     Pn-1
  = 1.03(1.03(1.03Pn-3))  Substitute
     Pn-2
               : Observe pattern
  =  
  =  

7.2 Solving Linear Recurrence Relations

We have seen how to find solutions, closed form expressions, for recurrence relations of the two forms with some constant C:

an = an-1 + C

an = Can-1

 

Finding solutions, closed form expressions, for recurrence relations takes practice and is still difficult for all but the simplest relations.

The section presents methods for finding solutions for special cases, we will examine one.

Definition 1

Linear homogenous recurrence relation of degree k with constant coefficients is a recurrence relation of the form:

an =  c1an-1 +  c2an-2 + ... + ckan-k

where c1, c2, c1, ..., ck are reals and ck is not 0.

Definition

Homogenous when all terms are multiples of aj.

an =  c1an-1 +  c2an-2 + ... + ckan-k

has k terms so is degree k.

 

Degree is number of terms of the sequence.

an =  c1an-1 +  c2an-2 + ... + ckan-k

has k terms so is degree k.

Example

Pn = 1.11Pn-1

degree 1

c1 = 1.11

 

an = 3an-1 - an-2

degree 2

c1 = 3

c2 = 1

 

an = 3an-5

     = 0an-1 + 0an-2 +0an-3 +0an-4 + 3an-5

degree 5

c5 = 3

 

an = 3a2n-1

Not linear, quadratic

 

an = 3an-1+ 2

Not homogenous, factor 2

 

an = nan-1

Not homogenous, coefficient not constant

 

Solving Linear Homogenous Recurrence Relations with Constant Coefficients

Linear homogenous recurrence relations occur often in modeling problems and can be systemically solved.

Theorem 1 - When two roots, r1 and r2

{an} is a solution of an = c1an-1  +  c2an-2

iff an = α1r1n  +  α2r2n for n=0,1,2,...,

where r2 - c1r - c2 = 0 has two distinct roots r1 and r2,

with constants α1 and  α2

 

Example 1 - (Question 3a, Section 7.2) What is the solution (closed form) of

By substitution

an = 2an-1

a0 = 3

an = 2an-1   an-1 = 2an-2
  = 2(2an-2)    
  =  22an-2    
  =  22(2an-3)   an-2 = 2an-3
        :    
  =  2n a0    
  = 3*2n    

By Theorem 1

1.    The recurrence relation and initial conditions

an = 2an-1 + 0an-2 for  n≥1

a0 = 3

an = c1an-1  +  c2an-2             Theorem 1

c1= 2, c2 = 0

a1 = 2a0 + 0a0 = 2*3 = 6

a2 = 2a1 + 0a0 = 2*6 +0*3 = 12

2.   Determine if there are two distinct roots, r1 and r2.

r2 - c1r - c2 = 0

r2 - 2r - 0 = (r-2)(r+0) = 0

r1 = 2

r2 = 0

3.    Using initial conditions and roots, solve

an = α1r1n  + α2r2n for α1 and α2

an = α1r1n  +  α2r2n
  = α12n  +  α20n
  for constants α1 and  α2
a0 = 3
  = α1r10  +  α2r20
  = α120  +  α200
  = α1 + α2
α1 + α2 = 3
a1 = 6
  = α1r10  +  α2r20
  = α121  +  α201
  = 2α1
2α1 = 6
α1 = 3

4.    α1, α2 - solve simultaneous linear equations using substitution:

Know

α1 + α2 = 3

α1 = 3

α1 + α2 = 3  
3 + α2 = 3 Substitute α1 = 3
α2 = 0 Subtract 3 from both sides

5.    an = α1r1n  +  α2r2n

Solve an by substituting α1,α2,r1n, r2n

r1 = 2, r2 = 0, α1 = 3, α2 = 0

an = α1r1n  +  α2r2n
  = 3*2n  + (0)0n
  = 3*2n

6. Verify    an = 3*2n

a0 = 3*20
  = 3
a1 = 3*21
  = 6

 

Example 2 - What is the solution (closed form) of

1. an = an-1+ 2an-2

a0 = 2, a1 = 7

c1= 1, c2 = 2

2. r2 - c1r - c2 = 0

r2 - r - 2 = (r+1)(r-2) = 0

r1 = 2, r2 = -1

3. Using initial conditions and roots, solve

an = α1r1n  + α2r2n for α1 and α2

an = α1r1n  +  α2r2n
  = α12n  +  α2(-1)n
for constants α1 and  α2
a0 = 2
  = α1r10  +  α2r20
  = α120  +  α2(-1)0
  = α1 + α2
α1 + α2 = 2
a1 = 7
  = α1r11  +  α2r21
  = α121  +  α2(-1)1
  = 2α1 -  α2
2α1 -  α2 = 7

4. α1, α2 - solve simultaneous linear equations using substitution:

     α1 + α2 = 2
+ 2α1 -  α2 = 7
_________ ___
    3α1 = 9
    α1 = 3
Solve for α1

Add equations

to eliminate α2

 

 

Simplify
α1 + α2 = 2 Solve for α2
3 + α2 = 2 Substitute α1
α2 = 2 - 3 Subtract
α2 = -1  

5. an = α1r1n  +  α2r2n

Solve an by substituting α1,α2,r1n, r2n

r1 = 2, r2 = -1, α1 = 3, α2 = -1

an = α1r1n  +  α2r2n
  = 3*2n  +  (-1)-1n
  = 3*2n + (-1)n+1

6. Verify

a0 = 3*20 + (-1)0+1
  = 3 + (-1)
  = 2
a1 = 3*21 + (-1)1+1
  = 6 + (1)
  = 7

Question 7.8

an = 7an-1 - 10an-2

a0 = 2

a1 = 1

a. What are c1 and c2?

b. Find the roots, r1 and r2.

r2 - c1r - c2 = 0

c. Using initial conditions and roots, solve

an = α1r1n  + α2r2n for α1 and α2

a0 = α1r10  + α2r20 = 2

a1 = α1r11  + α2r21 = 1

d. Find α1, α2 - solve simultaneous linear equations using substitution.

e. Solve an by substituting α1,α2,r1n, r2n

an = α1r1n  +  α2r2n

f. Verify by:

a0 = 2 = α1r10  +  α2r20

a1 = 1 = α1r11  +  α2r21

 

Theorem 2 - When one root

{an} is a solution of an = c1an-1  +  c2an-2

iff an = α1r0n  +  α2nr0n for n=0,1,2,..., where r2 - c1r - c2 = 0 has one root r0, with constants α1 and  α2

Example - What is the solution (closed form) of

an = 6an-1- 9an-2

a0 = 1, a1 = 6

c1= 6, c2 = -9

r2 - 6r + 9 = (r-3)(r-3) = 0

r0 = 3

an = α1r0n + α2nr0n = α13n + α2n3n

for constants α1 and  α2

a0 = 1 = α1r00  +  α20r00 = α130 = α1

a1 = 6 = α1r01  +  α2nr01 = α131  +  α21*31 = 3α1 + 3α2

α1 = 1

3α1 + 3α2 = 6

3α1 + 3α2 = 6
 3 + 3α2 = 6
3α2 = 3
α2 = 1

α2 = 1

an = α1r0n + α2nr0n = α13n + α2n3n = 3n + n3n

a0 = 3n + n3n  = 30 + 0*30 = 1

a1 = 3n + n3n = 31 + 1*31 = 3 + 3 = 6