Prove the following recurrence.

A full binary tree is a tree in which every node other than the leaves has two children. Let $$K_n$$ be the number of full binary trees with $$n+1$$ leaves. Show that $$K_n = \sum_{i=0}^{n-1}K_{i}K_{n-1-i}.$$

I thought of splitting the tree by its root node into sub-trees with maybe $$i$$ and $$n-i$$ nodes, but I am not sure how to prove this recurrence formally. Any ideas?

• Use induction. First show that the formula is true for $n=1$. Then induct: prove that if the formula is true for $n$, then it's true for $n+1$. – Nick Nov 16 '18 at 17:53

Your idea is probably the best way of doing this and there are not a lot of useful formalities to put on top of it. To convince you of this, I will end this post by showing you a proof in excessively formal language (although you'll see where it could be worse!) so that you see it really adds nothing but notation.

The notion of "proving something formally" is, for most purposes^, a myth that us teachers tell our into-to-proofs students to try to get them to write clearer arguments. I guess the intention of this post is: you should accept counting arguments like "choose the left subtree and right subtree" as not just meaningful, but essentially valid proofs.

Of course, when writing, you want to take pains to be convincing. Usually, this just means to anticipate the points most likely to be confusing, and address them explicitly in the text. When we first start out, we are extremely bad at understanding what is likely to be confusing. We get better if (and only if) we invest huge amounts of time, practice, and feedback.

With regards to this specific question, a decent example of an argument that I find convincing is given in Larry's answer to a slightly disguised variant. If you do not find it convincing (or you suspect a grader wouldn't), it is a worthwhile exercise to expand it in the places that you feel deserve more care.

I'm going to deal with most [see below] of the ambiguity in the question by writing a lemma:

Lemma: Let $$T$$ be a full binary tree with root $$r$$ and $$n+1\geq 2$$ leaves. Then

• $$T-r$$ is graph with two connected components, each of which is a full binary tree.
• The root of one component $$C_L$$ is the left child of $$r$$, and the root of the other component $$C_R$$ is the right child of $$r$$.
• If $$C_L$$ has $$i+1$$ leaves, then $$0\leq i\leq n-1$$, and $$C_R$$ has $$n-i$$ leaves. (*)
• For any full binary tree $$T'$$ with $$C_L'$$ and $$C_R'$$ defined analogously, if $$C_L'=C_L$$ and $$C_R'=C_R$$, then $$T=T'$$.

Assuming you're trying to be very formal: the exact statement of the lemma, and the proof that you write, will depend on exactly what your definition of a binary tree is. (For me, a binary tree is an acyclic connected graph with each edge labelled $$L$$ or $$R$$ denoting which side the children are connected on— and I'm eliding over the distinction between a connected component and a graph, and equality vs. isomorphism issues.)

[ But also, assuming you're being very formal, the statement given is false: there are no full binary trees with $$1$$ leaf, so $$K_0=0$$, but the formula relies on the convention that $$K_0=1$$. The exact statement of (*) may depend on how you fix this. You may enjoy spotting all of the places that this mangled initial condition ruins the proof below. ]

I'm not going to prove this lemma because I value my sanity (a little). Once you have the lemma, the proof goes like this:

Denote by $$\mathcal T_{n,i}$$ the number of full binary trees (FBTs) with $$n+1$$ leaves whose $$C_L$$ as defined in the lemma have $$i+1$$ leaves, and $$K_{n,i}=|\mathcal T_{n,i}|$$. Then $$K=\sum_{i\geq 0}K_{n,i}$$ by the Addition Principle; moreover $$K=\sum_{i=0}^{n-1} K_{n,i}$$ since the lemma guarantees that the omitted terms each vanish.

We claim that $$K_{n,i}=K_iK_{n-1-i}$$; for this we establish that $$T\mapsto (C_L, C_R)$$ is a bijection $$\mathcal T_{n,i} \to \left\{(A,B): A\text{ and }B\text{ are FBTs having }i+1\text{ and }n-1\text{ leaves respectively}\right\},$$

from which the result follows by recognizing the left side as a Cartesian product and then applying the Product Principle.

Injectivity is precisely the fourth bullet point from the lemma; we need to show that it is surjective as well. Let $$A$$ and $$B$$ be two FBTs with $$i+1$$ leaves and $$n-i$$ leaves, respectively. Call their roots $$a$$ and $$b$$. Let $$T$$ be the graph with \begin{align*} V(T) &= V(A)\cup V(B)\cup \{r\} \\ E(T) &= E(A)\cup E(B)\cup \{ra,rb\} \end{align*} Here, $$r$$ must not be a vertex of either $$A$$ or $$B$$. We leave as exercise to the reader that $$T$$ is a FBT when (e.g.) we interpret $$a$$ as the left child of $$r$$ and $$b$$ as the right child of $$r$$. Since $$r$$ is not a leaf, and $$a$$ and $$b$$ are not leaves of $$A$$ and $$B$$, we see that $$T$$ has $$(i+1)+(n-i)=n+1$$ leaves. As another exercise, show that the two connected components of $$T-r$$ are $$C_L=A$$ and $$C_R=B$$. Since $$(A,B)$$ was chosen arbitrarily from the codomain, this shows surjectivity.

It is a pleasure to state that this boring proof is over.

[ ^ There exist humans who work with formal theorem provers and so actually have seen a respectable proposition (e.g. of this complexity) proven at the level of true logical formalism. Formality beyond that level gets extremely philosophical, and I'm nowhere near qualified, so I'll drop it now. ]

• Thank you to the kind soul who upvoted this; your gift of internet points consoles me, that my torment for the last two hours was not in vain. – aleph_two Dec 24 '18 at 6:29
• Hey, thank you very much for writing this answer! – model_checker Dec 24 '18 at 14:52