A ternary tree is a tree where each node has at most three children. Prove that for every $n \geq 1$, every non-empty ternary tree of height $n$ has at most $\dfrac{(3^n − 1)}{2}$ nodes.
I am confused what to do here, can someone explain me the question and how to solve it by induction?
The case where $n=1$ is clear. Suppose the hypothesis holds for some $n \geq 1$. Then for the case of a ternary tree of height $n+1$ we have the subtree $n$ with at most $\frac {(3^{n}-1)}{2} $ nodes. For the extension of the tree at step $n+1$ we see that each of previous nodes in step $n$ can have at most $3$ child nodes by the definition of a ternary tree. So for the $n+1$ case we have $\frac{3^{n}-1}{2} + 3($# of nodes at step $n$ of the tree$) \leq \frac{3^{n}-1}{2} + 3(3^{n-1})=\frac{3^{n}-1}{2} + 3^{n} = \frac{3^{n}-1}{2} +\frac{2(3^{n})}{2} = \frac{3(3^{n}) -1}{2}=\frac {3^{n+1}-1}{2}$.
Hence, the maximal number of nodes for a tree of height $n+1 \leq \frac{3^{n+1}-1}{2}$. The first inequality with $3^{n-1}$ comes from the fact that this problem can be transformed into one concerning a finite geometric series, more specifically the following series: $1+3+3^2+...+3^{n-1}+3^n$ for a tree of height $n+1$.
