Recursive formula for a tree problem Question:

A binary is defined as a tree in which 1 vertex is the root, and any other vertex has 2 or 0 children. A vertex with 0 children is called a node, and a vertex with 2 children is called an inner vertex.
The order between the children is important.
A binary tree can be defined with recursion:
a binary tree is one out of 2 options :

*

*A single vertex.

*A vertex in which two sub-trees, that were build before, are connected to him.

Now, let $D_n$ be the number of valid binary trees, >with $n$ inner vertices.
For this question, a binary tree is called $valid$ if for each inner vertex $v$, the left sub-tree connected to $v$ in the left side, contains an even amount (0,2,4,...) of inner vertices.
Find the recursive formula with starting conditions for $D_n$ such that the formula can use all values before. In addition, calculate $D_6$.


$Solution.$ in order to build a valid binary tree of size $n$ we can take all options for a valid binary tree of size $n-1$ and take all options for a valid binary tree of size $n-2$. Therefore, we get: $$D_n=D_{n-1}+D_{n-2}$$
For the starting conditions: we consider $D_1$ which is 1 because we have only the root, which has an even amount of inner vertices (0).
For $D_2$ we have the next tree:

Therefore, $D_2=1$.
Calculation for $D_6$: $$D_6=D_5+D_4=D_4+D_3+D_3+D_2=D_3+D_2+(D_2+D_1)\cdot 2 + D_2=D_2+D_1+D_2+2D_2+2D_1+D_2=5D_2 +3D_1=5+3=8 $$

Now, I am not sure that this is correct, thus, I will be glad for some help. I think that might be better to convert this problem to another problem, but I think that this is good too. Thanks!
 A: A tree $t$ is valid if and only if the subtrees $t_1, t_2, t_3, \ldots$ represented in the figure below are valid and contain an even number of internal nodes
$\qquad$ 
Let $T_n$ be the set all of valid trees with $n$ internal nodes and let $T_{n,k}$ be the set of trees from $T_n$ with $k$ internal nodes on their rightmost branch. Then $T_n$ is the disjoint union of the $T_{n,k}$ for $1 \leqslant k \leqslant n$. Moreover, a tree of $T_{n,k}$ can be constructed, as explained in the figure, from valid trees $t_1, \ldots, t_k$ each of them having an even number of internal nodes. It follows that
$$
D_n = |T_n| = \sum_{1 \leqslant k \leqslant n} |T_{n,k}| \quad\text{and}\quad |T_{n,k}| =  \sum |T_{n_1}| |T_{n_2}| \cdots |T_{n_k}|
$$
where the second sum runs over all sequences of even numbers $n_1, \ldots, n_k$ such that $n_1 + \dotsm + n_k + k = n$.
Let us compute the first values, starting from $D_1 = 1$ and $D_2 = 1$. The set $T_2$ only contains the tree
$\qquad$ 
and $T_3$ contains the two trees
$\qquad$
Next $T_4$ contains the three trees
$\qquad$ 
and $T_5$ contains the seven trees


Thus $D_1 = 1$, $D_2 = 1$, $D_3 = 2$, $D_4 = 3$ and $D_5 = 7$, which already shows that the conjectured formula $D_n = D_{n-1} + D_{n-2}$ is wrong. Computation gives $D_6 = 12$, $D_7 = 30$, $D_8 = 55$, $D_9 = 143$, $\ldots$, which matches the A047749 OEIS sequence.
Thus it seems that
$$
D_n = \begin{cases}
\frac{1}{2m+1} \binom{3m}{m}&\text{if $n = 2m$}\\
\frac{1}{2m+1} \binom{3m+1}{m+1}&\text{if $n = 2m+1$}
\end{cases}
$$
but this formula remains to be proved.
A: this answer is not correct as J-E-pin pointed out
my take on this question:
it's pretty easy to see that $D_1 = 1$ and $D_2 = 1$.
we use these two as our bases.
we can create a valid tree with n internal vertex in one of two methods:

*

*take a tree with n-1 internal vertexes and replace its rightmost node with $D_1$,
this way we get an n-sized tree while maintaining the required properties, adding
$D_1$ to any other node will create an invalid tree.


*take a tree with n-2 internal vertexes and replace its leftmost node with $D_2$,
this way we get an n-sized tree while maintaining the required properties, adding
$D_2$ to any other node will create an invalid tree.
so we got: $D_n = D_{n-1} + D_{n-2}$
