# Proof by induction

Printable View

• May 15th 2009, 06: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 $b$ denote a fixed positive integer. Prove the following statement by induction: For every integer $n \geq 0$, there exist non-negative integers $q$ and $r$ such that

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

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

$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, 06: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 $b$ denote a fixed positive integer. Prove the following statement by induction: For every integer $n \geq 0$, there exist non-negative integers $q$ and $r$ such that

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

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

$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 $n=qb+ r,$ where $q \geq 0, \ 0 \leq r < b.$

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