Question

(6 points) Use repeated substitution to find an exact (non-asymptotic) closed-form ex- pression (a non-recursive function of n) for the recurrence F(n) - 12 F(n-1)+2 n2 2 Show your work, and write your final answer in the box at the bottom of the page.

Answer 1

f(n) = 2 f(n - 1) + 2^n = 2[2f(n - 2) + 2^n - 1] + 2^n = 2^2 f(n - 2) + 2^n + 2^n = 2^2 f(n - 2) + 2 middot 2^n = 2^2(2f(n - 3) + 2^n - 2) + 2 middot 2^n = 2^3 f(n - 3) + 2^n + 2 middot 2^n = 2^3 f(n - 3) + 3 middot 2^n = 2^k f(n - k) + k middot 2^n we know that f(n - k) = 2 if K = n - 1. f(n) = 2^n - 1 f(n - (n - 1)) + (n - 1)2^n = 2^n - 1 f(1) + (n - 1) middot 2^n f(1) = 2 given f(n) = 2^n - 1 middot 2 + (n - 1)2^n = 2^n + (n - 1)2^n = n middot 2^n f(n) = n middot 2^n