Prove by math induction

Tagged: 

This topic contains 1 reply, has 2 voices, and was last updated by  Tarit Goswami 4 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.