1. [10 marks] For the following recurrence, prove using the substitution method (i.e. induction) that T(n) = O(2n). You can assume that no = 1, and the exact form of induction isT(n) c2". ifn=1 T(n - 1) 2 ifn>1 7(n) = Note that you should also show for what values of constant c this inequality holds just like any other Big-O proof