Select Page

# Prove by math induction

Home Forums Math Olympiad, I.S.I., C.M.I. Entrance Number Theory Prove by math induction

Tagged:

This topic contains 1 reply, has 2 voices, and was last updated by  Tarit Goswami 2 months ago.

Viewing 2 posts - 1 through 2 (of 2 total)
• Author
Posts
• #21252

swastik pramanik
Participant

Prove by induction that the product n(n+1)(n+2)……..(n+r-1) of any consecutive r numbers is divisible by r!…

#21601

Tarit Goswami
Participant

Assume $$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

Viewing 2 posts - 1 through 2 (of 2 total)

You must be logged in to reply to this topic.