Question

Prove by mathematical induction that а. h log2 for any binary tree with height h and the number of leaves I b. h > log3 ] for any ternary tree with height h and the number of leaves I.

Answer 1

Answer: * To prove that by using mathematical Induction, @ h= [log,l] for any binary tree with heighth and the number of leaves ! :- * By using Mathematical Induction, ha [logge] > From that - alzl - [hao] , la no.of leaves Where ha Proof: — → Base care: - From @ [h=0) NOW, Take hao = 221, It is true. → General proof:- 2121 #let assume that alloze holds for any binary tree whose height doesn't Exceed'h * Let congider an arbitary binary tree T of height . hahtl * let congider Subtrees T= TLTR

* Where To left subtrees - Te = Right Subtrees * Here, The heights of T and TR Can't Exceed h. ie, ah z llic) [T, and TR one of them Dot both, can be empty] so, if ah? AITU) if not empty at is true [ By inductive assumption) otherwire (ITC) =0 is empty, i.e. il smallar than ah. * Similarly for l(TR)) oh selTR) i ett) = e(TL)+L(TR) [-T=TetTe] sahtah * 3 A(T) = ght! ; It if true Now, Tokong binary logrithm on both sides - zhal log2 (2h) > loque ..ha log24 Hence, it is proved by using mathematical Induction.

= h el logol) for any ternary tree with height h and the number of leaves li- * By using Mathematical Induction, ha [logge] © From that ahol [hzo] * prook: - Base Case - from ② Take h=0 ) 321, It iſ true. → Genevad proof: zhal 3hse, height of tree doesn't exceeds h. so, an arbitary binary tree haht! No, T=Tute ie, 3h = 1) * If Itte) is not empty 3h2 lite) r& true By using induction otherwile 1TL)=0 is empty.i.e. The value il smallar than sh. Similarly for ALTR), 3hs e(TR)

-; llT) = 11TL)+(Te) < 3h +3h = 3htl; It is true * so, ghze flow, apply logarithm on both sides log₂ (3h) z logze lih (10932] . Therefore, it il proved by wring Mathematical Induction