Problem 4. (10 MARKs) Recursive functions Consider the following recursively defined functiorn T(n) -ci aT(n 1) +bT(n - 2) n2 2 where a, b are real numbers Denote (*) the following relation T(n) = aT(n-1) + bT(n-2) n 2 We say a function f(n) satisfies (*) iff f(n) = af(n-1) + bf(n-2) is a true statement for n >2 Prove the following (i) For all functions f, g : N R, for any two real numbers , , if f(n) and g(n) (ii) Let q 0 be a real number. Show that if f(n) - q" satisfies (*) for n2 2 then (iii) State and prove the converse of (ii). Use this statement and part (i) to show satisfy (*) for n 2 2 then also h(n) - af(n) + Pg(n) satisfies it for n 2 2 q is a root of quadratic equation x2-ax-b that if q, g2 are the roots of r2 -az b 0 then h(n)A 0 Bq satisfies (*) for any two numbers A, B (iv) Consider h(n) from part (iii). What additional condition should we impose on the roots q1, q2 so h(n) serves as a closed-form solution for T(n) with A, B uniquely determined? (v) Use the previous parts of this exercise to solve the following recurrence in closed form T(n)-17 5T(n -1)-6T(n - 2) n2 2 Problem 4. (10 MARKs) Recursive functions Consider the following recursively defined functiorn T(n) -ci aT(n 1) +bT(n - 2) n2 2 where a, b are real numbers Denote (*) the following relation T(n) = aT(n-1) + bT(n-2) n 2 We say a function f(n) satisfies (*) iff f(n) = af(n-1) + bf(n-2) is a true statement for n >2 Prove the following (i) For all functions f, g : N R, for any two real numbers , , if f(n) and g(n) (ii) Let q 0 be a real number. Show that if f(n) - q" satisfies (*) for n2 2 then (iii) State and prove the converse of (ii). Use this statement and part (i) to show satisfy (*) for n 2 2 then also h(n) - af(n) + Pg(n) satisfies it for n 2 2 q is a root of quadratic equation x2-ax-b that if q, g2 are the roots of r2 -az b 0 then h(n)A 0 Bq satisfies (*) for any two numbers A, B (iv) Consider h(n) from part (iii). What additional condition should we impose on the roots q1, q2 so h(n) serves as a closed-form solution for T(n) with A, B uniquely determined? (v) Use the previous parts of this exercise to solve the following recurrence in closed form T(n)-17 5T(n -1)-6T(n - 2) n2 2