[9 points] Let T(n) represent the number of recursive calls required by the algorithm to calculate An. Prove the following, using induction: For n>=5, T(n) >3n/5 . Note that you must clearly state, for each line in your proof, the reasoning behind it (i.e. how you got to that line from the line above it).

1) [11 points total] Consider the following variation of the Fibonacci numbers, called the Abid numbers, which are defined recursively as follows: Ao 0, Al-1, A2 _ 2, A3-3, A4 _ 4 and for n 5, An-An-1 +An-2 +An-5 + 2. So the Abid Sequence is 0, 1, 2, 3, 4,9, 16, 29, A recursive algorithm which finds the nth term in the Abid Sequence is the following: Problem: Determine the nth term in the Abid Sequence. Inputs: a nonnegative integer n. Outputs: abid, the nth term in the Abid Sequence. int abid (int n) if (n