In answering a question related to binary trees, I came up with the following recurrent relation:
Base cases:
$$ f \left (1 \right ) = 1 $$ $$ f \left (2 \right ) = 2 $$ Recurrent relations: $$ f(n) = {n-1 \choose \frac{n-1}{2} } \left [f \left (\frac{n-1}{2} \right ) \right ]^2 \; \; \; \; \text{if n is odd} $$ $$ f(n) = {n-1 \choose \frac {n}{2}} 2 f \left (\frac {n}{2} \right ) f \left (\frac {n}{2} - 1 \right )\; \; \; \; \text{if n is even} $$
Original question URL: https://stackoverflow.com/questions/18046003/questions-about-binary-search-tree See response containing explanations on how I got this recurrent relation.
Questions:
- Can we get a formula resolving this recurrent relation?
- Optionally, could you scrutinize my answer and confirm its correctness or point out where I erred?
Note: Assuming $$ n=2^m-1 $$ we would always get an odd number, thereby simplifying the relation.
