Results 1 to 2 of 2

Math Help - Proof by induction

  1. #1
    Junior Member
    Joined
    Sep 2007
    From
    Minnesota
    Posts
    37

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by ScottO View Post
    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 07:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 12:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum