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.
Follow the standard pattern of a proof by mathematical induction. Since you’re trying to prove a result for each $n\ge 0$, your base case is $n=0$: you must verify that a complete $k$-ary tree of depth $0$ has $$\frac{k^{0+1}-1}{k-1}=\frac{k-1}{k-1}=1$$ nodes. Then assume as your induction hypothesis that every complete $k$-ary tree of depth $n$ has $$\frac{k^{n+1}-1}{k-1}$$ nodes and try to use that hypothesis to prove that every complete $k$-ary tree of depth $n+1$ has
$$\frac{k^{(n+1)+1}-1}{k-1}=\frac{k^{n+2}-1}{k-1}$$
nodes. To do this, suppose that $T$ is a complete $k$-ary tree of depth $n+1$. You know that it consists of a complete $k$-ary tree $T_0$ of depth $n$ plus a level consisting entirely of leaves. By the induction hypothesis there are $$\frac{k^{n+1}-1}{k-1}$$ nodes in $T_0$. Suppose that there are $\ell$ leaves; then you want to show that
$$\frac{k^{n+1}-1}{k-1}+\ell=\frac{k^{n+2}-1}{k-1}\;.\tag{1}$$
In order to do this, you’ll have to figure out what $\ell$ is. If you don’t already know, I suggest that you draw complete $k$-ary trees of depth $3$ or $4$, say, for $k=2$ and $k=3$ and see how many nodes are in each level. The sizes of the levels in a complete $k$-ary tree grow in a very simple fashion, and once you spot the pattern, it’s very easy to prove by induction that it really does hold. And once you know what $\ell$ is in terms of $k$ and $n$, it’s pretty easy to verify $(1)$.
Best Answer
Let $n+1=2^k$. A tree with height $\lfloor\log_2{n}\rfloor=k-1$ and $2^k-1$ nodes has to be complete binary since this is the maximum number of nodes you can have for the given height.
Now, if you remove a leaf which is not of greatest depth, then the resulting tree is not going to be complete binary, but it is going to contain $2^k-1$ nodes. This means that the height is higher than $k-1$, i.e. at least $k$, and we are done. The remaining case is when we remove a leaf of greatest depth, which is explained in your solution.