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
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.
Here is your statement:
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)$.