Results 1 to 2 of 2

Thread: Proof by induction

  1. #1
    Super Member
    Joined
    Oct 2007
    From
    London / Cambridge
    Posts
    591

    Proof by induction

    I know how to prove that the product n consecutive integers always has a factor of n! but i have found a problem that requires a proof of this by induction, any hints ?
    Last edited by bobak; Jan 24th 2008 at 03:44 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by bobak View Post
    I know how to prove that the product n consecutive integers always has a factor of n! but i have found a problem that requires a proof of this by induction, any hints ?
    Instead of writing, $\displaystyle a,a+1,a+2,...$ we will write $\displaystyle a_1,a_2,a_3,...$ because the notation is nicer. We will prove that if $\displaystyle a_1,\cdots ,a_n$ are consecutive integers then $\displaystyle n!$ divides $\displaystyle a_1\cdot \cdots \cdot a_n$. If $\displaystyle n=2,3$ then the proof is straightforward, this will be the base case an we will use induction on it. We assume that if we have any $\displaystyle k$ consecutive integers then $\displaystyle k!$ divides their product and prove that $\displaystyle (k+1)!$ divides any $\displaystyle k+1$ consecutive integers. In the proof we will use a simple result: $\displaystyle a_1\cdot \cdots a_{k+1} \equiv a_2 \cdot \cdots \cdot a_{k+2} (\bmod (k+1)!)$, let $\displaystyle A = a_2\cdot \cdots \cdot a_{k+1}$ then by induction $\displaystyle k!$ divides $\displaystyle A$ while $\displaystyle a_1 \equiv a_{k+2} (\bmod k+1)$ because $\displaystyle a_{k+2} = a_1 + (k+1)$, thus, $\displaystyle a_1 \cdot A \equiv A\cdot a_{k+2}(\bmod (k+1)!)$ and we proven this result. This result is simply saying that a product of $\displaystyle k+1$ consecutive integers is divisible by $\displaystyle (k+1)!$ if and only if the product of $\displaystyle k+1$ integers shifted one integer over is divisible by $\displaystyle (k+1)!$. We this we can finally prove this result. Remember we need to prove that $\displaystyle (k+1)!$ divides $\displaystyle a_1\cdot \cdots \cdot a_{k+1}$. If $\displaystyle k+1$ divides $\displaystyle a_1$ then $\displaystyle k!$ divides $\displaystyle a_2\cdot \cdots a_{k+1}$ (by induction) and so $\displaystyle (k+1)! = (k+1)k!$ divides $\displaystyle a_1\cdot \cdots \cdot a_{k+1}$. If $\displaystyle k+1$ does not divide $\displaystyle a_2$ then shift the sequence over enough times until the first term of the newly formed sequence is divisible by $\displaystyle k+1$ and repeat the argument. Q.E.D.
    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: Oct 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: Mar 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Oct 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum