# Math Help - Proof by induction

1. ## 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 ?

2. Originally Posted by bobak
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, $a,a+1,a+2,...$ we will write $a_1,a_2,a_3,...$ because the notation is nicer. We will prove that if $a_1,\cdots ,a_n$ are consecutive integers then $n!$ divides $a_1\cdot \cdots \cdot a_n$. If $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 $k$ consecutive integers then $k!$ divides their product and prove that $(k+1)!$ divides any $k+1$ consecutive integers. In the proof we will use a simple result: $a_1\cdot \cdots a_{k+1} \equiv a_2 \cdot \cdots \cdot a_{k+2} (\bmod (k+1)!)$, let $A = a_2\cdot \cdots \cdot a_{k+1}$ then by induction $k!$ divides $A$ while $a_1 \equiv a_{k+2} (\bmod k+1)$ because $a_{k+2} = a_1 + (k+1)$, thus, $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 $k+1$ consecutive integers is divisible by $(k+1)!$ if and only if the product of $k+1$ integers shifted one integer over is divisible by $(k+1)!$. We this we can finally prove this result. Remember we need to prove that $(k+1)!$ divides $a_1\cdot \cdots \cdot a_{k+1}$. If $k+1$ divides $a_1$ then $k!$ divides $a_2\cdot \cdots a_{k+1}$ (by induction) and so $(k+1)! = (k+1)k!$ divides $a_1\cdot \cdots \cdot a_{k+1}$. If $k+1$ does not divide $a_2$ then shift the sequence over enough times until the first term of the newly formed sequence is divisible by $k+1$ and repeat the argument. Q.E.D.