Proofs, Recursion and Analysis of AlgorithmsProperties of recurrence relationsOrder of Recurrence RelationSolving recurrence relationsExpand, guess and verifyVerification Step for Expand, Guess & VerifyClass ExerciseSolution from a formulaSlide 9Proofs, Recursion and Analysis of AlgorithmsMathematical Structures for Computer ScienceChapter 2Copyright © 2006 W.H. Freeman & Co. MSCS Slides Proofs, Recursion and Analysis of AlgorithmsSection 2.5 Recurrence Relations 2Properties of recurrence relationsA linear recurrence relation can be written as S(n) = f1(n)S(n-1) + f2(n)S(n-2) + …..+ fk(n)S(n-k) + g(n)where f’s and g are or can be expressions involving n.Linearity, homogeneity and orders A linear relation is when the earlier values in the definition of S(n) as shown above have power 1.The term linear means that each term of the sequence is defined as a linear function of the preceding terms.Example: F(n) = F(n-1) + F(n-2)A nonlinear relation is the one that has earlier values in the definition as powers other than 1.Example: F(n+1) = 2nF(n-1)(1-F(n-1))Solutions are quite complex.Homogenous relation is a relation that has g(n) = 0 for all nExample: a(n) – a(n-1) = 2nInhomogenous relation:Example: S(n) = 2S(n-1)Section 2.5 Recurrence Relations 3Order of Recurrence RelationA recurrence relation is said to have constant coefficients if the f’s are all constants. Fibonaci relation is homogenous and linear: •F(n) = F(n-1) + F(n-2)Non-constant coefficients: T(n) = 2nT(n-1) + 3n2T(n-2)Order of a relation is defined by the number of previous terms in a relation for the nth term.First order: S(n) = 2S(n-1) •nth term depends only on term n-1Second order: F(n) = F(n-1) + F(n-2)•nth term depends only on term n-1 and n-2 Third Order: T(n) = 3nT(n-2) + 2T(n-1) + T(n-3)•nth term depends only on term n-1 and n-2 and n-3Section 2.5 Recurrence Relations 4Solving recurrence relationsSolving a recurrence relation employs finding a closed-form solution for the recurrence relation.An equation such as S(n) = 2n, where we can substitute a value for n and get the output value back directly, is called a closed-form solution.Two methods used to solve a recurrence relation:Expand, Guess Verify•Repeatedly uses the recurrence relation to expand the expression for the nth term until the general pattern can be guessed. •Finally the guess is verified by mathematical induction.Solution from a formula•Known solution formulas can be derived for some types of recurrence relations.Section 2.5 Recurrence Relations 5Expand, guess and verifyShow that S(n) = 2n for the following recurrence relation:S(1) = 1S(n) = 2S(n-1) for n  2Expansion: Using the recurrence relation over again everytimeS(n) = 2S(n-1) S(n) = 2(2S(n-2)) = 22S(n-2) S(n) = 22(2S(n-3)) = 23S(n-3)Looking at the developing pattern, we guess that after k such expansions, the equation has the form S(n) = 2kS(n-k) This should stop when n-k =1, hence k = n-1, As the base case provided is S(1)S(n) = 2n-1S(1)  S(n) = 2.2n-1 = 2nDo the verification step by assuming the closed form solution for S(k) and proving S(k+1)Section 2.5 Recurrence Relations 6Verification Step for Expand, Guess & VerifyConfirm derived closed-form solution by induction on the value of n. Statement to prove: S(n) = 2n for n  2. For the basis step, S(l) = 21. This is true since S(1) is provided in the problem. Assume that S(k) = 2k. Then S(k+1) = 2S(k) (by using the recurrence relation definition) S(k+1) = 2(2k) (by using the above inductive hypothesis)  S(k+1) = 2k+1 This proves that our closed-form solution is correct.Section 2.5 Recurrence Relations 7Class ExerciseFind the solution for the following recurrence relation: T(1) = 1T(n) = T(n-1) + 3 for n  2 Solution:T(n) = T(n-1) + 3 = [T(n-2)+3] + 3 = T(n-2)+2*3 = [T(n-3)+3] + 2*3 = T(n-2) + 3*3In general, we guess that T(n) = T(n-k) + k*3When n-k = 1, i.e. k = n-1T(n) = T(1) + (n-1)*3 = 1 + (n-1)*3 = 3*n-2Prove the above by induction: T(1) = 3(1)-2 = 1, trueAssume T(k) = 3*k-2, show T(k+1) = 3*(k+1) +1 = 3*k+1T(k+1) = T(k) + 3 from the given recurrence relationT(k+1) = 3*k-2+3 by inductive hypothesisHence, T(k+1) = 3*k+1Section 2.5 Recurrence Relations 8Solution from a formulaSolution formula for linear first order constant coefficient relationS(n) = f1(n)S(n-1) + f2(n)S(n-2) + …..+ fk(n)S(n-k) + g(n)For the relation S(n) = 2S(n-1), we have f1(n) = 2 and g(n) = 0So, S(n) = cS(n-1) + g(n)S(n) = c[cS(n-2)+g(n-1)] + g(n) = c[c[cS(n-3)+g(n-2)] + g(n-1)] + g(n)..S(n) = ckS(n-k) + ck-1g(n-(k-1)) + …..+ cg(n-1) + g(n)The lowest value of n-k is 1Hence, S(n) = cn-1S(1) + cn-2g(2) + cn-3g(3) +….+ g(n)For S(n) = 2S(n-1), c = 2 and g(n) = 0Hence, S(n) = 2n-1*S(1) = 2.2n-1 = 2n since S(1) = 2€ S(n) = cn−1S(1) + cn−ig(i)i= 2n∑Section 2.5 Recurrence Relations 9Class ExerciseShow that the solution for the recurrence relationS(n) = 2S(n-1) + 3 for n  2 and given S(1) = 4 Here, g(n) = 3 and c = 2given by Show that the solution for the recurrence relationT(n) = T(n-1) + (n+1) for n  2 and given T(1) = 2 Here, g(n) = 1 and c = n+1given bySolutions for these exercises is in the text (pg. 151-152) € S(n) = 2n +1+ 3 2n−1−1[ ]€ T(n) = 2n +1+ 3 2n−1−1[