Math Olympiad, I.S.I. Entrance and College Mathematics › Forums › Math Olympiad, I.S.I., C.M.I. Entrance › Number Theory › Prove by math induction

- AuthorPosts
- April 23, 2018 at 1:46 pm #21252
Prove by induction that the product n(n+1)(n+2)……..(n+r-1) of any consecutive r numbers is divisible by r!…

June 17, 2018 at 8:54 am #21601Assume \( k! | P(m,k) \) for all \(m+k\le n\). Now to show that \( k! | P(m,k) \) for all \( m+k \le n+1 \)

If \( m=1\) we are done since \( P(1,k) = 1\cdot 2\cdots k = k!\) and if \( k=1\) then \( k! = 1!\), clearly divides \( P(m,k)\). So in the remainder

we may assume that \( m\ge 2\) and \( k \ge 2\). Also if \( m+k\le n\) we are done vacuously, so consider only that \( m+k = n+1\).

By the lemma we have $$P(m,k) = k\times P(m,k-1) + P(m-1,k)$$ so by the Induction hypothesis we have \( (k-1)! | P(m,k-1)\)

and thus also \( k! | k\times P(m,k-1)\) and also by the Induction hypothesis \( k! | P(m-1,k) \) and finally \( k! | P(m,k)\) QED

- This reply was modified 7 months, 1 week ago by Tarit Goswami.

- AuthorPosts

You must be logged in to reply to this topic.