Answer Happy

1. [7 points] Consider the following statement P(n) defined for all positive integers n: n n 1 i(i + 1)n +1 i=1 Use mathematical induction to prove P(n) for all integers n 2 1. 2. [7 points] Let a = 2, az = 9, and an = 2an-1 + 3 an-2 for n 2 3. Using strong induction, show that an < 3" for all positive integers n. 3. Below is a recursive definition of a function f(n) from the set of nonnegative integers to the set of integers: Basis step: f(0) = 2, f(1) = 3 Recursive step: f(n) = 3 x fin-1) - 5 x fin-2) for n 2 2 (a) [3 points] Find f(3). Show all steps leading to your answer. (b) [4 points] Give a pseudocode of a recursive algorithm for computing the value of the function f(n). Use the header below and fill out the body of the procedure. procedure funcfin: nonnegative integers)