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 ?

Printable View

- Jan 24th 2008, 09:12 AMbobakProof 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 ?

- Jan 25th 2008, 08:38 AMThePerfectHacker
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.