# Proof: By Induction

• By hypothesis, $T(V,E)$ is a tree with $|V|$ vertices and a given root $r$.
• Let $h$ be the height of $T$ with respect to $r$, let $d$ be the degree of $T$ with respect to $r$, and let $l$ denote the number of leaves in $T$.
• We prove the inequalities by induction on the height $h.$
• Base case $h=0$:
• Induction step $h\to h+1$
• Assume, for all trees $T^\prime$ with heights $h^\prime\le h$ we have the inequalities * $l^\prime\le d^{h^\prime}$ * $|V|\le 2\cdot d^{h^\prime}$ * $h^\prime\ge\log_d({l^\prime}).$
• Let $T(V,E)$ be a tree of height $h+1$.
• We prove $l+1\le d^{h+1}$: * Note that the leaves at the altitude $h+1$ of a tree $T$ have leaves of $T^\prime$ as their predecessors. * Since $T$ is of degree $d,$ each leaf of $T^\prime$ can have at most $d$ new successors (leaves) in $T.$ * It follows $l+1\le d\cdot d^{h}=d^{h+1}.$
• We prove $|V|\le 2\cdot d^{h+1}$ * We have just shown that at most $d^{h+1}$ new vertices in $T$ can be added at the altitude $h+1$. * The overall number of vertices in $T$ can be, therefore, estimated as $|V|\le 2d^h+d^{h+1}\le d^{h+1}+d^{h+1}=2d^{h+1}.$
• We prove $h+1\ge\log_d({l+1})$: * Since $l+1\le d^{h+1}$, it follows $\log_d(l+1)\le h+1$

Github: ### References

#### Bibliography

1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition