2. (a) (5 points) Suppose a function f(n) is defined by the following recursive
ID: 3168311 • Letter: 2
Question
2. (a) (5 points) Suppose a function f(n) is defined by the following recursive formula. f(n) = f(n-1) + f (n - 2) +15 f(0) =0, f(1)-5 , Use the guess-and-check method to get a closed-form formula for f(n). That is, guess a formula for f(n) and use induction to prove that your guess is correct (b) (5 points) Suppose a function g(n) is defined by the following recursive formula g(n) g(n-1) + 2n + 2, g(0) = 0. Use the unraveling method to get a closed-form formula for g(n). Make sure to show your work.Explanation / Answer
Solution: Take n = 2, f(2) = (5 + 0 + 15) /2 = 10, similarly f(3) = 15, f(4) = 20 and so on. So suppose f(n) = 5n.
Now for n=1, f(1) = 5,given. Let for n = k, f(k) = 5k, then for n = k+1, f(k+1) = { f(k) + f(k-1) + 15 } /2
i.e. f(k+1) = {5k + 5(k-1) + 15 } /2 i.e. 5(k+1) . Hence proved.
(b) g(1) = g(0) + 2.1 + 2 = 0+2+2 = 4, g(2) = 4+4+2 = 10, g(3) = 10+6+2 = 18, g(4) = 18+8+2 = 28
here we get the first difference as 4,6,8,10,.... & second difference as 2,2,2,2,....
since second difference is constant so the g(n) will be of form an2 + bn + c
now by putting, n=1 in this formulla, we get g(1) = a+b+c = 4 again g(2) = 4a+2b+c = 10 and g(3) = 9a+3b+c = 18
by solving these three equations we get : a=1, b= 3, c= 0
thus g(n) = n2 + 3n. we can also verify it by induction as above part.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.