Let M(h) be the minimum number of nodes in an AVL tree of height h. In such a tree it can be shown that M(h) = M(h-1) + M(h-2) + 1. [You don’t need to know why to answer this question but it is based on the minimum nodes in the left subtree and right subtree plus the root.] Now using this fact, prove using mathematical induction that M(h) = F(h+3) – 1 where F(0) = 0, F(1) = 1, F(x) = F(x-1) + F(x-2) for x>1.

## Expert Answer

M(h) = M(h-1) + M(h-2) +1

We need to prove by induction

M(h) = F(h+3) – 1 Where F{0} = 0, F(1) = 1, F(x) = F(x-1) + F(x-2)

The basic step h = 0 , we get M(h) as follows:

M(0) = F(3) -1

= F(2) + F(1) -1

= F(1) + F(0) + F(1) -1

= 1 + 0 + 1 -1

= 1 (Which is true)

Let us assume this holds for h = k then we need to prove for k+ 1 that

M(k+1) = F(k+4) – 1

Proof:

M(k+1) = M(k) + M(k-1) + 1 // As per the fact

= F(k+3) -1 + F(k+2) -1 + 1 As per the assumption which is true up to h=k

= F(k+3) + F(k+2) – 1

= F(k+4) -1 // As F(x) = F(x-1) + F(x-2)

Hence proved