Prove that there exist at most $4^n$ pairwise non-isomorphic trees on $n$ vertices.
I proceed by Induction,
Let $n=1$ then we have only one tree on $1$ vertex which is less than $4$.
Now assume that there exist at most $4^n$ pairwise non-isomorphic trees on $n$ vertices.
Let us consider a graph on $n+1$ vertices.
Now there are at most $4^n$ pairwise non-isomorphic trees on $n$ vertices.
How can I show that there will be at most $4^{n+1}$ pairwise non-isomorphic trees on $n+1$ vertices?
Any help.
Best Answer
I'm unconvinced that there's a simple induction argument.
We can prove this via the Catalan numbers: the $n^{\text{th}}$ Catalan number $C_n$ counts the number of ordered trees with $n+1$ vertices (rooted trees with an ordering on the children of each node). This is an upper bound on the ordinary number of trees, since any tree can be given at least one ordering. We know that $C_n = \frac1{n+1}\binom{2n}{n}$, so $$ C_n = \frac1{n+1}\binom{2n}{n} \le \binom{2n}{n} \le \sum_{k=0}^{2n} \binom{2n}{k} = 2^{2n} = 4^n < 4^{n+1} $$ shows the result you want. (Being more careful lets us bound the number of trees by $O(4^n/n^{5/2})$, but this is not terribly interesting, because the true base of the exponent is smaller than $4$.)