the number of nodes in binomial tree of order is function of knotes theorem- the binomial tree of order kbkcontains nodes extbfproof (by inductionlet nk be the number of nodes in bka binomial tree of order base caseby definitionb consists single node therefore inductive hypothesisassume that nk for lfor some > consider the binomial tree of order bl {rb bltherefore the number of nodes in bl+ is given by nl+ ni = = - + thereforeby induction on lnk for all > it follows from theorem that binomial trees only come in sizes that are power of two nk { furthermorefor given power of twothere is exactly one shape of binomial tree theorem- the height of bkthe binomial tree of order kis extbfproof (by inductionlet hk be the height of bka binomial tree of order base caseby definitionb consists single node therefore inductive hypothesisassume that hk for lfor some > consider the binomial tree of order bl+ {rb bltherefore the height bl+ is given by hi hl+ max <= <= max <= <= thereforeby induction on lhk for all > theorem tells us that the height of binomial tree of order is and tells us that the number of nodes is nk thereforethe height of bk is exactly (log nfigure shows that there are two ways to think about the construction of binomial treesi binomial bk consists of root node to which the binomial trees bk- are attached as shown in figure (alovely professional university