Mathematics

Total Marks = 40
1. Find the recurrence equation of the following algorithm and then solve the recurrence to find its time complexity as a closed form solution. Use iteration method to solve the recurrence. (10 marks)
Algorithm:
Test(A[1..n], B[1..n], C[1..n])
{
if n= 0 then return;
For i := 1 to n do
C[1] := A[1] * B[i];
Test(A[2..n], B[2..n], C[2..n]);
}
2. Prove the following using mathematical induction:?????(15 marks)
1. (ab)n = an bn?for every natural number n
2. 13 +23+33+…+n3 = (1+2+3+…+n)2
3. 1+3+5+7+…+(2n-1) = n2

3. Prove or disprove the following:???????(15 marks)
?1. lgvn ? O(lg n)?(vn means square root of n)
?2. lg n ? O(lgvn)
?3. 2n+1 ? O(2n)