Proving a binary tree has at most $lceil n/2 rceil$ leaves

Given a binary tree with $n$ nodes, prove that it contains at most $leftlceil frac{n}{2} rightrceil$ leaves.

Let us work with the tree definition $mathrm{Tree}= mathrm{Empty}mid mathrm{Leaf} mid mathrm{Node}(mathrm{Tree},mathrm{Tree})$. For $T$ such a tree, let $n_T$ the number of nodes in $T$ and $l_T$ the number of leaves in $T$. You are correct to do this by induction, but you will need structural induction that follows the tree structure. For trees, this is often done as complete induction over the height $h(T)$ of the trees. The induction anchor has two parts. First, for $h(t)=0$ we have $T=mathrm{Empty}$ with $l_T=n_T=0$; the claim clearly holds for the empty tree. For $h(t)=1$, i.e. $T = mathrm{Leaf}$, we similarly have $l_T=1=leftlceil frac{n_T}{2} rightrceil$, so the claim holds for leaves. The induction hypothesis is: Assume that the claim holds for all (binary) trees $T$ with $h(T)leq k$, $kgeq 1$ arbitrary but fixed. For the inductive step, consider an arbitrary binary tree $T$ with $h(T)=k+1$. As $kgeq 1$, $T=mathrm{Node}(L,R)$ and $n_T = n_L+ n_R+1$. As $L$ and $R$ are also binary trees (otherwise $T$ would not be) and $h(L),h(R)leq k$, the induction hypothesis applies and have $qquad displaystyle l_L leq leftlceil frac{n_L}{2} rightrceil text{ and } l_R leq leftlceil frac{n_R}{2} rightrceil.$ As all leaves of $T$ are either in $L$ or $R$, we have that $qquad begin{align*} l_T &= l_L + l_R &leq leftlceil frac{n_L}{2} rightrceil + leftlceil frac{n_R}{2} rightrceil &leq leftlceil frac{n_L + n_R + 1}{2} rightrceil qquad (*) &= leftlceil frac{n_T}{2} rightrceil end{align*}$ The inequality marked with $(*)$ can be checked by (four way) case distinction over whether $n_L,n_Rin 2mathbb{N}$. By the power of induction, this concludes the proof. As an exercise, you can use the same technique to prove the following statements:

• Every perfect binary tree of height $h$ has $2^h-1$ nodes.
• Every full binary tree has an odd number of nodes.