• Mathematica

## Main Question or Discussion Point

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

Related MATLAB, Maple, Mathematica, LaTeX News on Phys.org
uart
You cant prove it because it's not true. You can disprove it with one counter-example

10+11+12=33

33 is not divisable by 3!

But 3! is 6.

matt grime
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.

uart
matt grime said:
isn't the *product* of 3 consecutive integers

arildno
Homework Helper
Gold Member
Dearly Missed
Don't be ashamed, uart; I made a much sillier mistake..

uart
arildno said:
Don't be ashamed, uart; I made a much sillier mistake..
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:
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.

Tide
Homework Helper
In a sequence of n consecutive integers, there must be at least one number divisible by j where j <= n.

thanks you for all your replies , I will try uart's methods , thank you again

............................
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

ie.
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

(a+2)(a+3)...(a+n+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:
::
Suppose the numbers in question are
(a+1)(a+2).....(a+n)
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!
::

TenaliRaman you are right ,

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

I can't finish it by M.I.

uart
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

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

Gokul43201
Staff Emeritus
Gold Member
This is a couple days late, but I think it works :

To prove : $(m)_n = m(m+1)(m+2)...(m+n-1)~||~n!~$ (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, $(M+1)..(M+N-1)(M+N) - M(M+1)..(M+N-1)$

$$= (M+N)[(M+1)..(M+N-1)] - M[(M+1)..(M+N-1)] = N[(M+1)..(M+N-1)]$$

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

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

So that gives $(M+1)_N = M_N + k(N!)$

But by assumption #(ii), $M_N~||~N!$.

So that gives $(M+1)_N~||~N!$, 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:
uart
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).

eg,
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:
thank you :rofl: :rofl: :rofl: :rofl:

I will try the method.