Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove by Mathematical induction , please help

  1. Oct 4, 2004 #1
    how to prove :

    the product of n consecutive positive integers is divisible by n!

    by using Mathematical induction , you can assume nCk is an integer ??

    it is in urgent , please help , thank you! :smile:
  2. jcsd
  3. Oct 4, 2004 #2


    User Avatar
    Science Advisor

    You cant prove it because it's not true. You can disprove it with one counter-example


    33 is not divisable by 3!
  4. Oct 4, 2004 #3
    But 3! is 6.
  5. Oct 4, 2004 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    but 33 isn't divisble by 3!, however, since 33 isn't the *product* of 3 consecutive integers, that's neither here nor there.
  6. Oct 4, 2004 #5


    User Avatar
    Science Advisor

    Doh silly mistake, I read it as sum instead of product.
  7. Oct 4, 2004 #6


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    Don't be ashamed, uart; I made a much sillier mistake..
  8. Oct 4, 2004 #7


    User Avatar
    Science Advisor

    Hehe, well after that mistake I thought I should at least solve it, which I just did. :)

    Here's a clue for 3.14lwy :

    There are two approaches you could take.

    - One would be to start with a (a+1) is divisible by 2! and then try to show the a (a+1) ... (a+n-1) divisible by n! implies that a (a+1) ... (a+n) is divisible by (n+1)! That is, induction on n.

    - The other approach is to start with 1 * 2 * 3 ... n is divisible by n! (a=1) and then try to prove that a (a+1) .. (a+n-1) divisible by n! implies that (a+1) (a+2) ... (a+n) is divisible by n!. That is, induction on a.

    I found the latter approach to be easier.
    Last edited: Oct 4, 2004
  9. Oct 4, 2004 #8
    Not sure if "you can assume nCk is an integer ??" is a question or a statement?, but ...

    If I had to do this exercise I would want to prove the following lemma. Then, I think the induction step of the proof would follow easily from it.

    For integers p and q, if p > q > 0 and p isn't evenly divisible by q then there exists an integer r such that p - q < r < p AND q evenly divides r.
  10. Oct 4, 2004 #9


    User Avatar
    Science Advisor
    Homework Helper

    In a sequence of n consecutive integers, there must be at least one number divisible by j where j <= n.
  11. Oct 5, 2004 #10
    thanks you for all your replies , I will try uart's methods , thank you again :smile:

    I have try the 2nd method for some time ,
    I stop at there :

    let P(a) be the prosition ' (a+1)(a+2)...(a+n) is divisible by n! '

    when a = 0 , it is true ,
    P(0) is true ,

    assume P(a) is true for a = 1 , 2 , 3 ... k , where k is some non-negative integers

    1*2*3*...*n = n!(N1)
    2*3*4*...*(n+1) = n!(N2)
    (a+1)(a+2)...(a+n) = n!(Na)

    when a = k+1


    I try to expand it

    = a^n
    + [1+2+...+(n+1)]a^(n-1)
    + [1*2 + 2*3 + ... + n(n+1)]a^(n-2)
    + [1*2*3 + 2*3*4 + (n-1)(n)(n+1)]a^(n-3)
    + ...
    + 1*2*3*...*(n+1)

    then i don't know how to do ....
    Last edited: Oct 5, 2004
  12. Oct 5, 2004 #11
    Suppose the numbers in question are
    in how many ways can u choose n numbers out of (a+n) numbers?
    this is C(a+n,n) = (a+n)!/a!n! =(a+1)(a+2)...(a+n)/n!
  13. Oct 5, 2004 #12
    TenaliRaman you are right ,

    but the problem ask me to do it by M.I.

    I can't finish it by M.I. :frown:
  14. Oct 6, 2004 #13


    User Avatar
    Science Advisor

    Hmmm, this problem is harder to do using MI than I thought. When I posted before I started scratching out a rough MI proof using the two starting points I mentioned above. The second one looked like it would just fall into place but when I just went to post the complete solution I realized that I just counldn't make one of the steps work. Sorry if I misled anyone :eek:

    BTW. I know I've solved this problem before based on the method that Tilde posted above, it's not mathematical induction though.
  15. Oct 6, 2004 #14


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This is a couple days late, but I think it works :

    To prove : [itex](m)_n = m(m+1)(m+2)...(m+n-1)~||~n!~[/itex] (a||b means a is divisible by b)

    Clearly, this is true for all m with n=1, and also for all n with m=1 (since n! || n!).

    Assume the above statement is true for (i) n = N-1 and all m, as well as for (ii) n = N and m = M.

    Now, [itex](M+1)..(M+N-1)(M+N) - M(M+1)..(M+N-1) [/itex]

    [tex]= (M+N)[(M+1)..(M+N-1)] - M[(M+1)..(M+N-1)] = N[(M+1)..(M+N-1)] [/tex]

    Using the notation developed in the first line, above, this may be written as [itex](M+1)_N - M_N = N(M+1)_{N-1}[/itex]

    Now, from assumption #(i), [itex](M+1)_{N-1}~||~(N-1)! [/itex] so the RHS of the previous equation may be written as [itex]Nk(N-1)! = k(N!)[/itex]

    So that gives [itex](M+1)_N = M_N + k(N!)[/itex]

    But by assumption #(ii), [itex] M_N~||~N! [/itex].

    So that gives [itex](M+1)_N~||~N! [/itex], or the statement is true for n = N and m = M+1.

    It follows that the statement is true for n = N and all m.
    Last edited: Oct 6, 2004
  16. Oct 7, 2004 #15


    User Avatar
    Science Advisor

    Good work Gokul43201. I think that's the key, you need to do it two dimensionally, with induction on both variables at the same time. When I tried to do induction on just one variable I came to an impass but I could see a way that used both variable would work.

    BTW this is the 2D solution I came up with,

    Let the proposition P(a,n) denote that a (a+1) ... (a+n-1) || n!

    You can show that assuming P(a+1,n) together with P(a,n+1) implies P(a+1,n+1).

    P(a,n+1) : a (a+1) ... (a+n) = r (n+1)! {for some integer r}

    P(a+1,n) : (a+1) (a+2) ... (a+n) = s n! {for some integer s}

    Now consider P(a+1,n+1),

    We need to show that (a+1)(a+2) ... (a+n+1) = t (n+1)! {for some integer t}

    LHS = a (a+1) .. (a+n) + (n+1) (a+1) ... (a+n) : {after expanding by the (a+n+1) term}
    = r (n+1)! + s (n+1)n! : {after substituting P(a,n+1) and P(a+1,n) respectively}
    = (r+s)(n+1)!

    Since it's easy to show that P(1,n) is true for all n and that P(a,1) is true for all a then the proof inductively follows for all a,n from P(a+1,n) and P(a,n+1) implies P(a+1,n+1).

    P(2,1) and P(1,2) implies P(2,2)
    P(2,2) and P(1,3) implies P(2,3)
    P(2,3) and P(1,4) implies P(2,4)
    ... etc to build up the second row P(2,n) and then repeat for P(3,n), P(4,n) etc.
    Last edited: Oct 7, 2004
  17. Oct 7, 2004 #16
    thank you :rofl: :rofl: :rofl: :rofl:

    I will try the method. :smile:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook