In this post, we prove the closed form of a nonlinear recurrence corresponding to the count of binary trees with nodes.
Suppose I have a binary tree of internal nodes, we can count all possible such configurations by looking at the tree like
where each internal subtree with nodes is a vertex plus two trees whose node-sum is , or
This is pretty fucking hard to solve. Here’s a way where we do not need to appeal to generating functions.
Let’s begin with a reasonable hypothesis: is a first order recurrence. After groping around for a while, we find that this is actually a nonlinear homogeneous recurrence:
Here’s the first couple of terms:
No obvious pattern yet, but if we look at the sequence , we see that it looks like
Notice how the primes in the denominator are exactly the right amount of spacing apart ( is 2 away from , 4 away from , etc). Furthermore, for the nonprime denominators, they are always a divisor of what the expected value there is supposed to be (for example, the in the number right before the ), this seems to suggest that there’s always an inverse affine factor between two elements of the sequence. Since the denominator of is , let’s conjecture that
In fact, the sequence looks really nice!
why, this is just the sequence , so we can pretty accurately guess that
Warning: This is a really tedious proof; the point is to construct a series that cancels out the on the denominator of at each step of the induction.
Proof: By strong induction, for some , suppose that we have already shown that .
Consider the series
In the case, this looks like
notice that we can flip the order of this series and add with itself to get
By appealing to the induction hypothesis on , we also have
So, above, we’ve derived the following:
Substituting the left into the right, we get
which concludes the proof.
This recurrence allows us to write
Notice that this is the same as