In this written assignment you will use induction to prove the runtime of the recursive implementation of Triangular Number show below. Notice that the n$-$th triangular number is obtained by adding n to the previous term. a$)(5$ points$)$ Write out the recursive form of the growth function, $T(n),$ for Triangular number Problem. $(5$ points$)$ Draw the recursion tree for Triangular Number. Label each node with

the runtime of a call to Triangular Number excluding the cost of the recursive calls.

Label the height of your tree in terms of $n.$

$(10$ points$)$ Based on your recursion tree, please give a hypothesis for the closed$-$

form tight upper bound of your growth function $($ie a hypothesis of the form $T(n)in$

$O(f(n))$ and in at most two sentences explain how you used your recursion tree to

come up with the hypothesis. Then please prove that your hypothesis is true for

ALL values of $n$ with Base Case and Inductive Case.