Doubt regarding binary trees and counting Question: 

A binary Tree T is semi-balanced, if for every node m  in T: 
$$
\frac{R(m)}{2} &lt;= L(m) &lt;= 2*R(m)
$$
where, L(m) is the number of nodes in the left sub-tree of m and

R(m) is the number of nodes in the right sub-tree of m. 

Write a recurrence relation to count the number of semi-balanced binary trees with N nodes.

My Attempt:

Let T(N) denote the number of semi-balanced trees with N nodes. 

For N = 1, T(N) = 1 (Trivial)

For N > 1, T(N) can be found by splitting N into 3 parts, a root, a left subtree and a right subtree, let M be the number of nodes in the left portion, then the N - M - 1 is the number of nodes in the right portion, so by the constraint in the question,

$$
\frac{N-1}{3} &lt;= M &lt;= \frac{2*(N-1)}{3}
$$

So for N > 1,$$
T(N) = \sum_{M=\frac{N-1}{3}}^{\frac{2*(N-1)}{3}} T(M) * T(N-M-1)
$$

However, the answer is given as,$$
T(N) = \sum_{M=\frac{N-1}{3}}^{\frac{2*(N-1)}{3}} 2 * T(M) * T(N-M-1)
$$

Why is there a factor of 2 in the solution?
I think your answer is correct. Without bothering with recursive relations, we can observe that the only semi-balanced binary trees are perfect trees.

In fact, the only semi-balanced binary trees of heights $1$ and $2$ respectively are perfect (obvious for height $1$, casework for height $2$). Now, assume by inductive hypothesis that all semi-balanced binary trees of height at most $n$ are perfect trees. By definition, the root of a semi-balanced binary tree of height $n+1$ must have two semi-balanced subtrees as children, one of which has height $n$. By inductive hypothesis, that subtree is exactly the perfect binary tree of height $n$. By inductive hypothesis and definition of semi-balanced binary tree, the other subtree must therefore be too the perfect binary tree of height $n$, which completes the proof.

We can see that for e.g. $N=7$ the presence of a factor $2$ yields a wrong answer.

Nitpicky thing: you should take the upper integer part of the lower limit of the sum, and the lower integer part of the upper limit.