CS 2210 Discrete Structures Advanced Counting Fall 2018 Sukumar Ghosh Compound Interest A person deposits $10,000 in a savings account that yields 10% interest annually. How much will be there in the account after 30 years? Let Pn = account balance after n years. Then Pn = Pn-1 + 0.10 Pn-1 = 1.1Pn-1 Note that the definition is recursive.

What is the solution Pn? Pn = Pn-1 + 0.10 Pn-1 = 1.1Pn-1 is a recurrence relation By solving this, we get the non-recursive version of it. Recurrence Relation Recursively defined sequences are also known as recurrence relations. The actual sequence is a solution of the recurrence relations. Consider the recurrence relation: an+1 = 2an (n > 0) [Given a1=1]

The solution is: an = 2n-1 (The sequence is 1, 2, 4, 8, ) So, a30 = 229 Given any recurrence relation, can we solve it? More examples of Recurrence Relations 1. Fibonacci sequence: an = an-1 + an-2 (n > 2) [Given a1 = 1, a2 = 1] What is the formula for an? 2. How many bit strings of length n that do not have two

consecutive 0s. For n=1, the strings are 0 and 1 For n=2, the strings are 01, 10, 11 For n=3, the strings are 011, 111, 101, 010, 110 Do you see a pattern here? Example of Recurrence Relations Let an be the number of bit strings of length n that do not have two consecutive 0s. This can be represented as an = an-1 + an-2 and

(why?) [bit string of length (n-1) without a 00 anywhere] 1 [bit string of length (n-2) without a 00 anywhere] 1 0 (an-1) (an-2) an = an-1 + an-2 is a recurrence relation. Given this, can you find an? Tower of Hanoi

Transfer these disks from one peg to another. However, at no time, a larger disk should be placed on a disk of smaller size. Start with 64 disks. When you have finished transferring them one peg to another, the world will end. Tower of Hanoi Let, Hn = number of moves to transfer n disks. Then Hn = 2Hn-1 +1 (why?) Can you solve this and compute H64? (H1 = 1)

Solving Linear Homogeneous Recurrence Relations A linear recurrence relation is of the form an = c1.an-1 + c2. an-2 + c3. an-3 + + ck. an-k (here c1, c2, , cn are constants) Its solution is of the form an = rn (where r is a constant) if and only if r is a solution of rn = c1.rn-1 + c2. rn-2 + c3. rn-3 + + ck. rn-k This equation is known as the characteristic equation. Example 1 Solve: an = an-1 + 2 an-2 (Given that a0 = 2 and a1 = 7)

Its solution is of the form an = r n The characteristic equation is: r2 = r + 2, i.e. r2 - r - 2 = 0. It has two roots r = 2, and r = -1 The sequence {an} is a solution to this recurrence relation iff an = 1 2n + 2 (-1)n a0 = 2 = 1 + 2 a1 = 7 = 1. 2 + 2.(-1) This leads to 1= 3, and 2 = -1

Example 2: Fibonacci sequence Solve: fn = fn-1 + fn-2 (Given that f0 = 0 and f1 = 1) Its solution is of the form fn = rn The characteristic equation is: r = (1 + 5) and (1 - 5) r2 - r - 1 = 0. It has two roots

The sequence {an} is a solution to this recurrence relation iff fn = 1 ((1 + 5))n + 2 ((1 - 5))n (Now, compute 1 and 2 from the initial conditions): 1 = 1/5 and 2 = -1/5 The final solution is fn = 1/5. ((1 + 5)) - 1/5.((1 - 5)) n n Example 3: Case of equal roots

If the characteristic equation has only one root r0 (*), then the solution will be an = 1 r0n + 2 .nr0n See the example in the book. Example 4: Characteristic equation with complex roots Solve: an = 2.an-1 -2.an-2 (Given that a0 = 0 and a1 = 2)

The characteristic equation is: r2 - 2r + 2 = 0. It has two roots (1 + i) and (1 - i) The sequence {an} is a solution to this recurrence relation iff an = 1 (1+i)n + 2 (1-i)n (Now, compute 1 and 2 from the initial conditions): 1 = - i and 2 = i The final solution is an = -i.(1+i)n + i.(1-i)n Check if it works!

Divide and Conquer Recurrence Relations Some recursive algorithms divide a problem of size n into b sub-problems each of size n/b, and derive the solution by combining the results from these sub-problems. This is known as the divide-and-conquer approach Example 1. Binary Search: If f(n) comparisons are needed to search an object from a list of size n, then f(n) = f(n/2) + 2 [1 comparison to decide which half of the list to use, and 1 more to check if there

are remaining items] Divide and Conquer Recurrence Relations Example 2: Finding the maximum and minimum of a sequence f(n) = 2.f(n/2) + 2 Example 3. Merge Sort: Divide the list into two sublists, sort each of them and then merge. Here f(n) = 2.f(n/2) + n Divide and Conquer Recurrence Relations

Theorem. The solution to a recurrence relations of the form f(n) = a.f(n/b) + c (here b divides n, a 1, b >1, and c is a positive real number) is f(n) (if a=1) (if a >1) (See the complete derivation in page 530) Divide and Conquer Recurrence Relations PROOF OUTLINE. Given f(n) = a.f(n/b) + c

Let n=bk. Then f(n) = a.[a.f(n/b2)+c] + c = a.[a.[a.f(n/b3)+c]+c]+ c and so on = ak. f(n/bk) + c.(ak-1+ak-2++1) (1) = ak.f(n/bk) + c.(ak-1)/(a-1) = ak.f(1) + c.(ak-1)/(a-1) (2) Divide and Conquer Recurrence Relations

PROOF OUTLINE. Given f(n) = a.f(n/b) + c When a=1, f(n) = f(1) + c.k (from 1) Note that n=bk, k = logbn, So f(n) = f(1) + c. logbn [Thus f(n) = O(log n)] When a>1, f(n) = ak.[f(1) + c/(a-1)] + c/(a-1) [

] Divide and Conquer Recurrence Relations What if n bk? The result still holds. Assume that bk < n

Divide and Conquer Recurrence Relations Apply to binary search f(n) = f(n/2) + 2 The complexity of binary search f(n) (since a=1) What about finding the maximum or minimum of a sequence? f(n) = 2f(n/2) + 2 So, the complexity is f(n)

Master Theorem Note that there are four parameter: a, b, c, d