0
$\begingroup$

enter image description here

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 enter image description here

Source: Discrete Mathematics with Applications, Susanna S. Epp

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ P(n) is the sentence "there exist integers q and r such that n = dq + r and 0≤r<d. But in your proof of p(n) is true in case of n ≥ d there is "q+1" in "n=d(q+1)+r and 0≤r<d" in place of "q" That doesn't seem neat. I think there needs some substitution to change q+1 to q. $\endgroup$
    – buzzee
    Feb 23, 2016 at 19:25
  • $\begingroup$ I disagree on that. If $q$ is an integer then so is $q+1$ and that (i.e. the fact that it is an integer) is the only thing that counts. The naming of these integers is completely irrelevant. $\endgroup$
    – drhab
    Feb 23, 2016 at 19:31
0
$\begingroup$

(1) $P(1), P(2) \dots, P(d)$ are true.

Because, if $0 \le k \le d-1$ then $k = 0 \cdot d + k$ proves $P(k)$ and if $k=d$ then $k = d\cdot 1 + 0$ proves $P(k)$.

(2) For all integers $k \ge 1$, if $P(i)$ is true for all integers $i$ from $1$ through $k$,then P(k+1) is also true.

We already know that if $1 \le k \le d$, then P(k+1) is true.

When $k=d$, then $k+1 = 1\times d + 1$, so P(d+1) is true.

So we can assume that $k \gt d$, in which case $1 \le k+1-d \le k$.

Hence, by our induction hypothesis, we know that $P(k+1-d)$ is true.

Then $k+1-d = dq + r$ for some $0 \le r \lt d$.

So $k+1 = (k+1-d) + d = (dq + r) + d = d(q+1) + r$

which implies P(k+1) is true.

$\endgroup$
2
  • $\begingroup$ Nice, but this proves actually: if some integer $n_0$ exists such that $P(n_0)$ is true then $P(n)$ is true for each integer $n\geq n_0$. So the proof is not complete yet. $\endgroup$
    – drhab
    Feb 24, 2016 at 9:06
  • $\begingroup$ I did not deny that. I agree with it and consequently it can be used to prove by induction exactly what I mention in my former comment: $P\left(n_{0}\right)\implies\forall n\geq n_{0}\left[P\left(n\right)\right]$. A full proof of $\forall n\in\mathbb{Z}\left[P\left(n\right)\right]$ still lacks. $\endgroup$
    – drhab
    Feb 24, 2016 at 14:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .