2. Prove using induction that a recurrence for the height of an AVL tree that leads to a tight bound (i.e., a lower constant factor). Let Th be an AVL tree of height h with a minimum number of nodes. Let N(h) be the number of nodes and NL(h) the number of leaves of Th. Recall that Th can be viewed recursively as a tree containing a root with two, possibly empty, subtrees Th1 and Th2. a) Prove that for any h1,N(h)=N(h1)+NL(h). b) Prove that for h0,NL(h)=F(h+1), where F (i) is the ith Fibonacci number. [F(0)=0, F(1)=1,F(n)=F(n1)+F(n2)] c) Prove that for h0,N(h)=F(h+3)1. You must use parts a ) and b) to prove c)