# Proof by induction

• May 15th 2009, 05:01 PM
ScottO
Proof by induction
Hi Folks,

I'm having difficulty making progress on the following proof, and I'm hoping for some hints to help me along.

Let $\displaystyle b$ denote a fixed positive integer. Prove the following statement by induction: For every integer $\displaystyle n \geq 0$, there exist non-negative integers $\displaystyle q$ and $\displaystyle r$ such that

$\displaystyle n = qb + r, 0 \leq r < b$.

So I can state the assertion and show the initial case is true:
$\displaystyle A(n): n = qb + r, 0 \leq r < b$

$\displaystyle A(0): 0 = 0 \cdot b + 0, n = q = r = 0$

I've tried picking a value for b and creating a table of related values for q and r as n counts up from 0. But I can't figure out how to express the patterns I see to form a usable general case and inductive step.

Again, just looking for hints right now to help get me out of the rut I'm in.

Thanks,
Scott
• May 15th 2009, 05:45 PM
NonCommAlg
Quote:

Originally Posted by ScottO
Hi Folks,

I'm having difficulty making progress on the following proof, and I'm hoping for some hints to help me along.

Let $\displaystyle b$ denote a fixed positive integer. Prove the following statement by induction: For every integer $\displaystyle n \geq 0$, there exist non-negative integers $\displaystyle q$ and $\displaystyle r$ such that

$\displaystyle n = qb + r, 0 \leq r < b$.

So I can state the assertion and show the initial case is true:
$\displaystyle A(n): n = qb + r, 0 \leq r < b$

$\displaystyle A(0): 0 = 0 \cdot b + 0, n = q = r = 0$

I've tried picking a value for b and creating a table of related values for q and r as n counts up from 0. But I can't figure out how to express the patterns I see to form a usable general case and inductive step.

Again, just looking for hints right now to help get me out of the rut I'm in.

Thanks,
Scott

this is a wrong subforum for this question. you should've posted it in pre-algebra or discrete math subforum. anyway, suppose $\displaystyle n=qb+ r,$ where $\displaystyle q \geq 0, \ 0 \leq r < b.$

thus $\displaystyle n+1=qb + r + 1.$ we have $\displaystyle r + 1 \leq b$ because $\displaystyle r < b.$ now if $\displaystyle r + 1 < b,$ then we're done and if $\displaystyle r+1=b,$ then $\displaystyle n+1=qb+b=(q+1)b,$ done again!