0
$\begingroup$

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

2 Answers 2

1

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.

  • 0
    Very clear, I think I get it now :)!2011-12-01
1

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)$.

  • 0
    Yes, $a,b,q,r$ are integers in this induction statement. And yes, the inductive step is really $P(a-b) \Rightarrow P(a)$.2011-12-01