I am considering binary trees (tree with at $\textbf{most}$ two children) $ where any 'left' and 'right' children components are considered distinct from each other. I simply want to understand the origin of the equation below as it helps me to understand other aspects of counting trees, and I use this equation a lot throughout my studies
Let $a_h$ be the number of possible distinct binary trees with height (tree level) of h, i.e. where $a_0=1, a_1=3 , a_2=21$ etc.
I want to show that $a_n=2a_{n-1}(1+a_0+a_1+a_2+...+a_{n-2})+a_{n-1}^2$ for all n $\geq$ 2.
$\textbf{My thoughts so far}$
I have been trying to logically describe how and why the number of possible trees of height h depends completely on how many possible trees there are for each of the previous generations in some way or another (like the above equation is showing) but I am struggling to directly match what the equation is saying with my own approach.
I am thinking along the lines of: the 2 in the equation must correspond to the fact that for any unique tree of height h-1, at any node you may add up to two more 'right and or left' nodes to make a unique tree of height h. This as well as realizing the nature of each previous set of unique trees of heights h-i all must directly influence how many there will be of h.
I am considering things like if you can add verticies to a leaf node on a tree of height h-1 to then make a tree of height h, how many ways can you do this, wnad what other ways are there to consider to make all possible height/level h trees such that the above equation can be yielded.
Any guidance would be appreciated.
This problem is naturally recursive (or "inductive" if you are not a CS person). Suppose you know the number of distinct binary trees with height $k$, for every $k<n$ Call this quantity $t_k$. To figure out $t_{n}$, consider the following procedure. Take any binary tree $T_{1}$ rooted at some node $r_1$ having height $k_{1}=n-1$, and some other binary tree $T_{2}$ rooted at node $T_{2}$ having height $0\leq k_{2}\leq n-1$. Add a new node $r$ that is adjacent to $r_1$ and $r_2$, the resulting tree is a binary tree of height $n$.
Since we consider the left and right subtree to be distinct, for each tree $T$ we produce, we can place $T_{1}$ as the right child or left child of $r$, so we get a factor of 2 here, except for the case where $T_{1}$ and $T_{2}$ are identical.
So, overall we can choose $T_{1}$ to be any binary tree of height $n-1$, of which there are $t_{n-1}$ such trees, and if we let $T_2$ be a binary tree of height at most $n-2$ then $T_{1}$ and $T_{2}$ are guaranteed to be distinct, so we have $$t_{n-1}(1+t_0+t_1+\dots +t_{n-2})$$ ways to do this, and for every such way, we can swap the positions of $T_{1}$ and $T_{2}$ resulting in a factor of two increase. Note that the 1 comes from the fact that we can choose $T_2$ or $T_1$ to be the empty tree.
For the case where $k_1=k_2=n-1$, we have $(t_{n-1})^2$ ways to choose $T_1$ and $T_2$ So, we have $(t_{n-1}^2)$ ways to choose such trees. All together, we get
$$t_{n}=2t_{n-1}(1+t_0+t_1+\dots +t_{n-2})+t_{n-1}^2$$