Algorithm Design ECS 122A
Popular in Course
Popular in Engineering Computer Science
This 2 page Class Notes was uploaded by Ashleigh Dare on Tuesday September 8, 2015. The Class Notes belongs to ECS 122A at University of California - Davis taught by Zhaojun Bai in Fall. Since its upload, it has received 56 views. For similar materials see /class/187716/ecs-122a-university-of-california-davis in Engineering Computer Science at University of California - Davis.
Reviews for Algorithm Design
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/08/15
Review of Linear Recurrence Relations 1 A recurrence relation for the sequence an is an equation that expresses an in terms of one or more of the previous terms of the sequence namely a0 a1 an1 for all integers n with n 2 no where no is a nonnegative integer The initial conditions for a sequence specify the terms that precede the rst term where the recurrence relation takes effect A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation to Exercise Let an 2an1 7 ang for n 23 4 Determine whether the following sequences are solutions a an 3n for every nonnegative integer n b an 2 for every nonnegative integer n c an 5 for every nonnegative integer n OJ A linear homogeneous recurrence relation of degree k with constant coe cients is a recurrence relation of the form an C171 6272 Ckan7k where c1 cg ck are real numbers and ck 7 O A consequence of the second principle of mathematical induction is that a sequence satisfying the above recurrence relation is uniquely determined by this recurrence relation and the k initial conditions a0 00 a1 Cl ak1 Ckil q THEOREM Let c1 and cg be real numbers Suppose that the characteristic equation r27c1r7cg 0 has two distinct roots r1 and rg Then the sequence an 010471 egang is a solution of the recurrence relation if and only if an 0417 agrg for n O 1 2 where 041 and ag are constants Proof two steps 0 Show that the sequence an with an 0417 04ng is a soliution 0 Show that if an is a solution then an 0417 agrg for some constants 041 and ag U Exercise What is the solution of the recurrence relation an an1 2ang with a0 2 and a1 a Exercise Find an explicit formula for the Fibonacci numbers fn fikl fikg with the initial conditions f0 0 and f1 1 7 THEOREM Let c1 and cg be real numbers with cg 7 0 Suppose that r2 7 cm 7 cg 0 has only one root r0 multiplicity is two Then the sequence an is a solution of the recurrence relation an 010471 egang if and only if an alrg 04gan for n O 1 2 where 041 and 042 are constants 00 Exercise What is the solution of the recurrence relation an 6044 7 gang with initial conditions a01anda167 H H 9 O to Linear nonhomogeneous recurrence relation with constant coef cients 1 where 0102 ck are real numbers and is a function not identically zero depending only on n The recurrence relation an Giana 6272 Ckanik an C1an71 62an72 Ckanik is called the associated homogeneous recurrence relation THEOREM lf alf l is a particular solution of Then every solution is of the form as m where agh is a solution of the associated homogeneous recurrence relation From the theorem7 we see that the key to solving the nonhomogenous recurrence relations is nding a particular solution Although there is no general method for nding such a solution for every function Fn7 we can make an educated guess for a certain types of functions Exercise Find all solutions of an 3an4 2n What is the solution with the initial condition a1 3 Hint try out a particular solution of the form on d7 where c and d are constants Exercise Find all solutions of an 5an4 7 Sang 7 Hint try out a particular solution of the form 07 for some constant c