Consider the following recurrence relations: (i) (3 MARKS) S(n) = {S(n - 1) if n=0 (S(n-1))2+2S(n-1)...

 

Transcribed Image Text:

Consider the following recurrence relations: (i) (3 MARKS) S(n) = {S(n - 1) if n=0 (S(n-1))2+2S(n-1) if n>0 Hint: let T(n)S(n) + 1, and try to find a closed form of T(n) first. (ii) (4 MARKS) 0, if n = 0 S(n) = 1, if n = 1 S(n-2)+2n-1 if n> 1 and n is even S(n-2)+3n if n > 1 and n is odd For each recurrence relation, please complete the following tasks: 1. Use repeated substitution to get the closed form for S(n). 2. Prove the closed form is correct using some form of induction. 3. Based on the closed form, state a conjecture for f(n) such that S(n) = (f(n)). 4. Prove the bound is correct. Consider the following recurrence relations: (i) (3 MARKS) S(n) = {S(n - 1) if n=0 (S(n-1))2+2S(n-1) if n>0 Hint: let T(n)S(n) + 1, and try to find a closed form of T(n) first. (ii) (4 MARKS) 0, if n = 0 S(n) = 1, if n = 1 S(n-2)+2n-1 if n> 1 and n is even S(n-2)+3n if n > 1 and n is odd For each recurrence relation, please complete the following tasks: 1. Use repeated substitution to get the closed form for S(n). 2. Prove the closed form is correct using some form of induction. 3. Based on the closed form, state a conjecture for f(n) such that S(n) = (f(n)). 4. Prove the bound is correct.