Let $B$ be the subset of $N=\{m_0,m_0+1,...\}$ such that $P(m)\iff m\in B$. This $B$ is not empty since for all $m_0\le m'<m_0$ the property $P$ is satisfied, thus also $P(m_0)$. We want to show that $B=N$. So assume that $A:=N\setminus B\ne\emptyset$. Then there is an $m\in A$ such that each $m_0\le n<m$ is in $B$, in other words $m$ is the minimum of $A$. But if $n<m$ implies $P(n)$, then by hypothesis $P(m)$ and so $m\in B$, a contradiction. Hence $B=N$.
Remark: This works for all sets $N$ where each non-empty subset has a minimal element with respect to a relation $R$. These sets are called well-founded.
If you want to use the hint, show that $Q(n)$ implies $Q(n+1)$ and that $Q(m_0)$: Since $Q(m')$ is true for all $m_0\le m'< m_0$, it is also true for $m_0$. Assume $n$ is a natural number $\ge m_0$ such that $Q(n)$. This means that $P(m)\ \forall m_o\le m<n$. By hypothesis this implies $P(n)$, thus $P(m)\ \forall m_0\le m<n+1$, so again by definition of $Q$ we have $Q(n+1)$. Now apply the induction principle.
So we can proof the strong induction principle via the induction principle. However, the normal induction principle itself requires a proof, it that is the proof I wrote in the first paragraph. As mentioned it works for all well-founded sets ($\mathbb N$ is such a set.)
You are proving this over induction on the Tree $T$, not the variables $b, x$, so we can assume we are just given values of $b$ and $x$, with $x < b$.
The base case of the induction is when $T = \text{Nil}$. So you have to prove:
- if $\text{less}(b, \text{Nil})$, then $\text{less}(b, \text{insert}(x, \text{Nil}))$.
So assume $\text{less}(b, \text{Nil})$. (Actually this much is true from the definition of "less" - but even if it were not always true, since it is your hypothesis, you can assume it here.)
By the definition of "insert", $$\text{insert}(x, \text{Nil}) = \text{Tree}(x, \text{Nil}, \text{Nil})$$
So you need to prove $\text{less}(b, \text{Tree}(x, \text{Nil}, \text{Nil}))$.
By the definition of "less", that statement is
$$\text{less}(b, \text{Tree}(x, \text{Nil}, \text{Nil})) = x < b \text{ and }\text{less}(b, \text{Nil})\text{ and }\text{less}(b, \text{Nil})$$
Since $x < b$ and $\text{less}(b, \text{Nil})$ are both true, so is $\text{less}(b, \text{Tree}(x, \text{Nil}, \text{Nil}))$ and therefore $\text{less}(b, \text{insert}(x, \text{Nil}))$.
This proves the base case. I'll leave you to figure out how to do the induction step.
On the inductive step, again, you can assume that $x, b \in \Bbb Z$ with $x < b$.
What you need to show is that for a tree $T \ne \text{Nil}, \text{less}(b, T) \implies \text{less}(b, \text{insert}(x,T))$. Because $T \ne \text{Nil}$, you know that $T = \text{Tree}(a, L, R)$ for some $a \in \Bbb Z$ and trees $L, R$.
The inductive hypothesis is (since we are given $x < b$), "$\text{less}(b, L) \implies \text{less}(b, \text{insert}(x,L))$ and $\text{less}(b, R) \implies \text{less}(b, \text{insert}(x,R))$"
So you start by assuming $\text{less}(b, T)$. From this, demonstrate that $\text{less}(b, L)$ and $\text{less}(b, R)$. By the induction hypothesis, you then know that $\text{less}(b, \text{insert}(x,L))$ and $\text{less}(b, \text{insert}(x,R))$. From those two facts, you then demonstrate that $\text{less}(b, \text{insert}(x,T))$ also holds. Once you've supplied the indicated demonstrations, this proves $\text{less}(b, T) \implies \text{less}(b, \text{insert}(x,T))$, finishing the inductions step.
Best Answer
By definition, notice that $p + q = k + 1$. By the induction hypothesis, the last two blocks required $p - 1$ and $q - 1$ fits, respectively. Adding in the last fit, we conclude that the total number of fits is: $$ (p - 1) + (q - 1) + 1 = (p + q) - 1 = (k + 1) - 1 = k $$ as desired.