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

- January 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 ?

- January 25th 2008, 08:38 AMThePerfectHacker
Instead of writing, we will write because the notation is nicer. We will prove that if are consecutive integers then divides . If 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 consecutive integers then divides their product and prove that divides any consecutive integers. In the proof we will use a simple result: , let then by induction divides while because , thus, and we proven this result. This result is simply saying that a product of consecutive integers is divisible by if and only if the product of integers shifted one integer over is divisible by . We this we can finally prove this result. Remember we need to prove that divides . If divides then divides (by induction) and so divides . If does not divide then shift the sequence over enough times until the first term of the newly formed sequence is divisible by and repeat the argument. Q.E.D.