# What induction hypothesis do they mean? (Proof of the Division Theorem)

I'm reading, but I can't get what induction hypothesis they are talking about on page 10 on http://www.win.tue.nl/~hansc/vena/webalt.pdf at Existence of q and r for nonnegative a and b. What do they mean?

Regards, Kevin

-

The induction hypothesis is (indirectly) stated just before the line The theorem holds if $|a|=0$: ‘A proof follows that proceeds by induction on $|a|$’. That’s why the first step is to prove that the theorem is true when $|a|=0$: that’s the smallest possible value for $|a|$. That takes care of the basis step of the induction $-$ of ‘getting the induction off the ground’.

Let $P(a,b)$ be the statement that there are unique integers $q$ and $r$ such that $a=bq+r$, $|r|<|b|$, and $ar\ge 0$. The basis step showed that $P(a,b)$ is true for all $b\in\mathbb{Z}\setminus\{0\}$ when $|a|=0$. Now you assume that $|a|>0$ and that $P(a',b)$ is true for all $b\in\mathbb{Z}\setminus\{0\}$ whenever $|a'|<|a|$; that’s the induction hypothesis that they’re talking about.

-
Very clear, I think I get it now :)! –  Kevin Dec 1 '11 at 19:40

Let $a,b$ be non-negative integers. Then there exists $q,r$ so that $0 \leq r < b$ and $$a=b \cdot q +r \,.$$
This statement is proven by (complete) induction on $a$; this is your $P(a)$.
Yes, $a,b,q,r$ are integers in this induction statement. And yes, the inductive step is really $P(a-b) \Rightarrow P(a)$. –  N. S. Dec 1 '11 at 20:41