My preferred definition of a non-empty, full binary tree is:
Definition 0. A pointed magma is an ordered triple $(X,\bullet,\star)$, such that:
- $X$ is a set
- $\bullet$ is an element of $X,$ and
- $\star$ is a function $X \times X \rightarrow X$.
Definition 1. Write $\mathbb{T}$ for the initial pointed magma, the elements of which are called non-empty full binary trees.
For example, here's an example of a non-empty full binary tree:
$$(\bullet \star \bullet) \star \bullet \in \mathbb{T}$$
This can be visualized as a tree, of course:
Okay. Let $\varphi : \mathbb{T} \rightarrow \mathbb{N}$ denote the node-counting function. Explicitly:
Definition 2. Define a function $\oplus : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ as follows: $$a\oplus b = a+b+1$$
Definition 3. Let $\varphi : (\mathbb{T},\bullet,\star) \rightarrow (\mathbb{N},1,\oplus)$ denote the unique such homomorphism of pointed magmas. We call $\varphi$ the node counting function.
For example, $$\varphi((\bullet \star \bullet) \star \bullet) = (1\oplus 1) \oplus 1 = 3 \oplus 1 = 5$$
So the above tree has $5$ nodes, as desired.
I claim that:
Claim. For all $x \in \mathbb{T}$, the natural number $\varphi(x)$ is odd.
This prove this, we need a way of performing induction on non-empty full binary trees. Here's a theorem that lets us do this:
Structural Induction for $\mathbb{T}$.
The pointed magma $(\mathbb{T},\bullet,\star)$ has no proper subalgebras.
More explicitly:
Structural Induction for $\mathbb{T}$. (Long form.)
Let $X$ denote a subset of $\mathbb{T}$.
If
- $\bullet \in X$, and
- for all $x,y \in X$, we have $x \star y \in X$,
then
$X = \mathbb{T}$.
Now we can prove our claim. Let $X$ denote the set of all $x \in \mathbb{T}$ such that $\varphi(x)$ is odd.
We know that $\bullet \in X$, since $\varphi(\bullet) = 1$ and $1$ is odd.
Assume $x,y \in X$. We will show that $x \star y \in X$. We know that $\varphi(x \star y) = \varphi(x) \oplus \varphi(y) = \varphi(x)+\varphi(y)+1.$ But the sum of three odd numbers is itself odd. So $\varphi(x \star y)$ is odd.
Hence by the structural induction theorem, we have $X=\mathbb{T}$. But recall that we defined $X$ as the set of all $x \in \mathbb{T}$ such that $\varphi(x)$ is odd. Thus $\mathbb{T}$ itself is the set of all $x \in \mathbb{T}$ such that $\varphi(x)$ is odd. In other words, $\varphi(x)$ is always odd, for all $x \in \mathbb{T}$. QED
A further comment.
It is worth noting that we can define the leaf-counting function in much the same way:
Definition 4. Let $\lambda : (\mathbb{T},\bullet,\star) \rightarrow (\mathbb{N},1,+)$ denote the unique such homomorphism of pointed magmas.
We call $\lambda$ the node counting function.
For instance, $$\lambda((\bullet \star \bullet) \star \bullet) = (1+1)+1 = 3,$$ so the aforementioned tree has $3$ leaves, as desired.
The cool thing about $\lambda$ is that it gives what is perhaps the most fundamental definition of the Catalan numbers; namely, writing $C_n$ for the $n$th Catalan number, we can define: $$C_n = |\lambda^{-1}(n+1)|$$
For example, $$C_2 = |\lambda^{-1}(3)| = |\{(\bullet \star \bullet) \star \bullet, \bullet \star (\bullet \star \bullet)\}| = 2$$
Best Answer
Let me make certain I understand you correctly, since you're using some terminology that's different from what I'm used to. (I'm used to roots of height $0$, and level and height of a node coinciding, but that clearly isn't the case for you.) It seems to me that if you're dealing with a tree of height $j$, then a node will be on level $c$ if and only if said node has height $j-c$. Is this accurate?
(As a side note, we require $k$ to be no greater than the height of the tree for the formula to work.)
Operating under the assumption that I am correctly interpreting you (until and unless you inform me otherwise), let me now talk about your proof. Your basis case is just fine. In the hypothesis case, you've correctly concluded from (1) that there are half as many nodes of height $m+2$ as there are of height $m+1$--however, this is not useful for the induction. Instead, we need to relate the number of nodes of height $m+1$--about which we would like to draw a conclusion--to the number of nodes of height $m$--about which we made the inductive hypothesis.
I suspect that what you actually meant was that there are half as many nodes of height $m+1$ as there are of height $m$. This is the correct observation to make, so long as $m$ is less than the height of the tree (which I take to be a hidden assumption). By inductive hypothesis, there are $$\left\lceil\frac{n}{2^{m+1}}\right\rceil$$ nodes of height $m$, and so by our observation, there are $$\frac12\cdot\left\lceil\frac{n}{2^{m+1}}\right\rceil$$ nodes of height $m+1$. Your task, then, is to show that $$\frac12\cdot\left\lceil\frac{n}{2^{m+1}}\right\rceil=\left\lceil\frac{n}{2^{m+2}}\right\rceil,$$ or equivalently, $$\left\lceil\frac{n}{2^{m+1}}\right\rceil=2\cdot\left\lceil\frac{n}{2^{m+2}}\right\rceil.\tag{&}$$
By definition, for any real $x$, $\lceil x\rceil$ is the least integer not less than $x$. Thus, we have $$\frac{n}{2^{m+1}}\le\left\lceil\frac{n}{2^{m+1}}\right\rceil<\frac{n}{2^{m+1}}+1\tag{#}$$ and $$\frac{n}{2^{m+2}}\le\left\lceil\frac{n}{2^{m+2}}\right\rceil<\frac{n}{2^{m+2}}+1.\tag{##}$$ Multiplying everything by $2$ in $(\#\#)$, we find that $$\frac{n}{2^{m+1}}\le 2\cdot\left\lceil\frac{n}{2^{m+2}}\right\rceil<\frac{n}{2^{m+1}}+2,$$ so by $(\#)$ there are only two possibilities to consider:
In any complete balanced binary tree, there are an even number of nodes on all but the $0$th level--a consequence of (1). Hence, since we assumed that $m$ was less than the height of the tree (so nodes of height $m$ are not on the $0$th level) and that $\left\lceil\frac{n}{2^{m+1}}\right\rceil$ is the number of nodes of height $m$, option (a) is the correct one, so $(\&)$ holds, as desired.