Question 3: Back to induction for recursive structures [5 points] Sometimes standard induction can be very useful to prove statements involving recursivelydened sets as long as we nd an appropriate quantity to induct 0n. Induct on the height of a tree to prove that any perfect binary rooted tree of height it has 2h+1 i 1 vertices. You may use weak (Le. standard) or strong induction but may not use structural induction