Given a binary tree $t$, prove that $size(t) < 2^{h(t)}$ I was able to prove that $size(t) \leq 2^{h(t)} - 1$ for any binary tree $t$, however I wasn't able to do anything reasonable with this statement.

I know it's a proof by induction and that the inductive hypothesis is the following:

$
size(l) &lt; 2^{h(l)} \\
size(r)  &lt; 2^{h(r)}
$

where $l$ and $r$ are the left and right subtrees of the tree $t = \langle l,v,r \rangle$. Usually what I'd do is start from $size(\langle l,v,r \rangle)$ and work my way up to $&lt; 2^{h(\langle l,v,r \rangle)}$. However I wasn't able.
If a binary tree has height $h$ then it has at most 1 node at depth 0, at most 2 nodes at depth 1, ..., at most $2^{h-1}$ nodes at depth $h-1$ (the maximal depth), and so at most $1+2+\cdots+2^{h-1} = 2^h-1$ nodes in total.

You can also prove this by induction. When $h=1$, the tree consists only of a root, so at most $1=2^h-1$ vertices. Given a tree of height $h$, its two subtrees have height at most $h-1$, and so together contain at most $2(2^{h-1}-1)$ vertices. Together with the root, the tree contains at most $2(2^{h-1}-1)+1=2^h-1$ vertices.