Question: Use mathematical induction to prove the existence part of the quotient-remainder theorem for integers $n ≥ 0$.
My attempt(edited):
Let the property $p(n)$ be the following sentence:
There exist integers $q$ and $r$ such that $n = dq + r$ and $0 \le r < d$
for any integer $n \color{red}{\ge 0}$ and any positive integer $d$".
Show that $p(0)$ is true
i"There exist integers $q=0$ and $r=0$ such that
$0 = d \cdot 0 + 0$ and $0 \le r=0 < d=1$ for any integer $n=0$ (?)
Show that for all integers $k$ with $ 0 \le k \le n-1$, if p(k) is true, then p(n) is true
$\color{gray}{But,\space [k = d \cdot 0 + k] \land [0 \le (r=k) < d] \Rightarrow q=0, r=k \in Z \space with \space r=k\ge 0}$
$\color{gray}{Hence,\space \forall k\in Z\space with\space r=k\ge 0,\space p(k)}$
Suppose, $p(k)$ is true for all integers $k$ from $0$ through $n-1$.
That is, an inductive hypothesis is there exist integers q, r
such that $(k=dq+r)\land (0\le r<d)$ for all integers k with $0 \le k \le n-1$
Then we must show $p(n)$ is true, i.e. "there exist integers q, r such that $n=dq+r\space\land\space 0\le r <d$".
Case 1 ($\color{red}{n < d}$):
There exist q=0, r=n such that $n = d \cdot 0 + n \land [0 \le (r=n) < d]$
Hence, p(n) is true in case 1.
Case 2 ($\color{red}{n \ge d}$):
since d > 0, $0\le n-d<n \Rightarrow 0 \le n-d < n \le n-1$ by inductive hypothesis
Hence, there exist integer q, r such that $n-d=dq+r \land 0\le r <d$
Hence, $n=d(q+1)+r \land 0\le r <d$ $\color{gray}{\text{I don't like the variable q+1 in this step. It doesn't seem neat}}$
Hence, p(n) is true in case 2.
Since p(k) is true in case 1, 2, p(k) is true for all integers $k \ge 0$
$\color{red}{Q.E.D}$
FYI
Source: Discrete Mathematics with Applications, Susanna S. Epp
Best Answer
Start by proving the theorem for nonnegative integers $n$.
If $n<d$ then we can take $q=0$ and $r=n$ to achieve:$$n=dq+r\text{ and }0\leq r<d$$
In your notation this means that $P(i)$ is true for $i=0,\dots,d-1$.
Our induction hypothese is that $P(k)$ is true for $k=0,\dots,n-1$ or shortly for nonnegative integers $k$ that satisfy $k<n$. On base of that it must be proved that $P(n)$ is true as well.
If $n\geq d$ then $0\leq n-d<n$ so the inductionhypothese says that integers $q$ and $r$ exist with $$n-d=dq+r\text{ and }0\leq r<d$$ That implies immediately that$$n=d(q+1)+r\text{ and }0\leq r<d$$
So $P(n)$ has shown to be true and we are allowed to conclude that $P(n)$ is true for each nonnegative integer $n$.
Now completing the proof for negative integers.
If $n<0$ then $n+md>0$ for some integer $m$ so integers $q$ and $r$ exist with $$n+dm=dq+r\text{ and }0\leq r<d$$ That implies immediately that$$n=d(q-m)+r\text{ and }0\leq r<d$$ Ready.