Proof by induction and height of a binary tree I need some help with a simple proof. I want to know if this proof is correct:
Let's define the height of a binary tree node as:


*

*0, if the node is a leaf

*1 + the maximum height of the children


The height of the tree is the height of the root. I have to prove by induction (for the height k) that in a perfect binary tree with n nodes, the number of nodes of height k is:
$$
\left\lceil \frac{n}{2^{k+1}} \right\rceil
$$
Solution:
(1) The number of nodes of level c is half the number of nodes of level c+1 (the tree is a perfect binary tree).
(2) Theorem: The number of leaves in a perfect binary tree is $ \frac{n+1}{2} $
Basis:
For  $ k=0 $ we have:
$$ \left\lceil \frac{n}{2} \right\rceil $$
Because the tree is perfect binary tree, n is odd, so:
$$
\left\lceil \frac{n}{2} \right\rceil = \frac{n+1}{2}
$$
That is true because of the theorem (2).
Hypothesis:
Let's suppose that the statement is true for $ k = m $, let's prove it for $m+1$
We have:
$$
\left\lceil \frac{n}{2^{m+2}} \right\rceil = \left\lceil \frac{\frac{n}{2^{m+1}}}{2} \right\rceil
$$
The number of nodes of height $ m+2 $ is half the number of nodes of height $ m+1 $ that is true because of (1)
Is it ok? Can I use the statement (2) to prove it or is not formally correct?
 A: 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:

(a) $\left\lceil\frac{n}{2^{m+1}}\right\rceil=2\cdot\left\lceil\frac{n}{2^{m+2}}\right\rceil$,
(b) $\left\lceil\frac{n}{2^{m+1}}\right\rceil=2\cdot\left\lceil\frac{n}{2^{m+2}}\right\rceil+1$.

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.
A: As long as you have proved theorem $(2)$ independently, there is no problem with using it. But your induction step and statement $(1)$ are slightly incorrect. Consider $n=6$ for example. It has $3$ nodes of height $0$ and $2$ of height $1$. Correct statement there would be that if $f(c)$ is number of nodes of height $c$, then $f(c+1) = \lceil \frac{f(c)}{2}\rceil$. 
