Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
Very clear, I think I get it now :)! –  Kevin Dec 1 '11 at 19:40

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

share|improve this answer
    
I only learned induction on integers. Am I correct? I read this: Suppose it holds for a-b, then it also holds for a. Since b was arbitrary, it holds for all a (in Z). –  Kevin Dec 1 '11 at 19:33
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.