KEMBAR78
Chapter 7. Advanced Counting Techniques | PDF | Recurrence Relation | Theoretical Computer Science
Scribd
Upload
306 views8 pages

Chapter 7. Advanced Counting Techniques

This document discusses advanced counting techniques, specifically recurrence relations. It defines a recurrence relation as an equation that expresses the nth term of a sequence in terms of previous terms. It provides examples of recurrence relations and their solutions. It then discusses techniques for solving both linear homogeneous and non-homogeneous recurrence relations algebraically by finding the characteristic equation and roots. The key steps are finding coefficients c1 and c2, solving the quadratic equation to get roots r1 and r2, defining the nth term involving r1 and r2, and determining coefficients by the initial conditions.

Uploaded by

hungkg
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
306 views8 pages

Chapter 7. Advanced Counting Techniques

This document discusses advanced counting techniques, specifically recurrence relations. It defines a recurrence relation as an equation that expresses the nth term of a sequence in terms of previous terms. It provides examples of recurrence relations and their solutions. It then discusses techniques for solving both linear homogeneous and non-homogeneous recurrence relations algebraically by finding the characteristic equation and roots. The key steps are finding coefficients c1 and c2, solving the quadratic equation to get roots r1 and r2, defining the nth term involving r1 and r2, and determining coefficients by the initial conditions.

Uploaded by

hungkg
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

Chapter 7. Advanced Counting Techniques 7.1 Recurrence Relations We study functions or sequences that can be recursively dened.

Basic counting principles:


A recurrence relation for sequence {an} is an equation that expresses an in terms of one of more of the previous terms of the sequence, namely a0 , a1 , . . . , an1 , for all integers n with n n0 , for some non-negative integer. A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relations.

Examples: a1 = 1, an = 2an1, n > 1.

Solution to this recurrence: 1, 2, 22, 23, . . . ,


1

Modeling with recurrence relations modeling problems (or solutions): example: Fibonacci sequence (just sequence) example: running time of recursive algorithms
binary search insertion sort quick sort

example: compound interest (solution) example: Tower of Hanoi (solution)

Solving recurrence relations using iteration techniques example: solving a1 = 1 an = 2an1 example: solving time function for binary search

B (n) = B (n/2) + 1

example: solving time function for the ideal case of quick sort

Q(n) = 2Q(n/2) + n

example: solving time function for the average case of quick sort Q(n) = Q(n/3) + Q(2n/3) + n
3

7.2 Solving Linear Recurrence Relations First we look at recurrence relations that are linear, homogeneous. Linear: left term is the sum of terms in the right (terms prior to the left term in the sequence)

Hn = 2Hn1 + 1 homogeneous: all terms in the right are terms preceding the left term Fn = Fn1 + Fn2

We explain the technique using Example: a0 = 2, a1 = 7, an = an1 + 2an2


The basic approach is to look for solutions of the form: an = r n, where r is a constant. Note that an = rn is a solution for recurrence if and only if rn = rn1 + 2r n2 we have rn rn1 2rn2 = 0 divided by rn2 , r2 r 2 = 0 solve it: (r 2)(r + 1) = 0 two roots: r1 = 2 and r2 = 1
n + rn. Try an = 1 r1 2 2

characteristic equation

a 0 = 2 = 1 1 + 2 1 a1 = 7 = 1 2 + 2 (1) Solve 1 = 3, 2 = 1 So: an = 3 2n (1)n.


5

Theorem 1 Let c1 , c2 be real numbers. Suppose that r 2 c1 r c2 = 0 has two distinct roots r1 and r2 . Then the sequence n + r n is a solution for recurrence {an}, where an = 1 r1 2 2 an = c1 an1 + c2 an2 where 1 , 2 are determined by the initial conditions of the recurrence.

Consider the previous example: a0 = 2, a1 = 7, an = an1 + 2an2 here c1 = 1, c2 = 2, plug into the theorem to solve it.
Note that changing the values of a0 , a1 may completely change the sequence, given the same recurrence. E.g., a0 = 1, a1 = 2. Then a 0 = 1 = 1 1 + 2 1 a1 = 1 = 1 2 + 2 (1) solve them: 1 = 1, 2 = 1/3 so an = 2n + 1/3(1)n, a dierent sequence.
6

Solving a recurrence step 1: nd out c1, c2; step 2: solving the quadratic equation to get roots r1 and r2;
n + rn step 3: dene an = 1r1 2 2

step 4: solving 1, 2 using initial conditions.

Theorem 2 Let c1 , c2 be real numbers. Suppose that r 2 c1 r c2 = 0 has a unique roots r . Then the sequence {an}, where an = 1 r n + 2 nrn is a solution for recurrence an = c1 an1 + c2 an2 where 1 , 2 are determined by the initial conditions of the recurrence.

Example: an = 2an1 an2 try dierent initial conditions: (1) a0 = a1 = 1; (2) a0 = 1, a1 = 2; (3) a0 = 2, a1 = 5;

You might also like