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.
So would it be correct for me to go to the lowest node in the lowest level subtree to the left (i.e. 5) and then use that node to overwrite the node I'm trying to delete? So essentially I overwrote the node I wanted to delete 4 with 5 then deleted node 5 and thus:
$c_1 =$ B.S.T. after deleting 4 and $c_2 = $ B.S.T. after deleting 10
so:
$c_1$:
and then for deleting 10 I find the smallest node in the right tree which is 11 and I overwrite 10 with that and then delete 11 so:
$c_2:$
Best Answer
I think the best way to go is to prove a more general property by induction.
Let $P(n)$ be: The number of ways in which $n$ numbers $x_1<x_2<\dots<x_n$ can be inserted in an empty binary search tree, such that the resulting tree has height $n-1$ is $2^{n-1}$
$P(1)$ is easy to prove.
Assume that $P(n)$ hold for some $n$ and show that $P(n+1)$ is true. small hint:
Then to prove your statement you use $P(7)$.
I hope it helps.