1. Oct 4, 2004

### 3.14lwy

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!

2. Oct 4, 2004

### 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!

3. Oct 4, 2004

But 3! is 6.

4. Oct 4, 2004

### matt grime

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

5. Oct 4, 2004

### uart

Doh silly mistake, I read it as sum instead of product.

6. Oct 4, 2004

### arildno

Don't be ashamed, uart; I made a much sillier mistake..

7. Oct 4, 2004

### uart

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
8. Oct 4, 2004

### CrankFan

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.

9. Oct 4, 2004

### Tide

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

10. Oct 5, 2004

### 3.14lwy

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: Oct 5, 2004
11. Oct 5, 2004

### TenaliRaman

::
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!
::

12. Oct 5, 2004

### 3.14lwy

TenaliRaman you are right ,

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

I can't finish it by M.I.

13. Oct 6, 2004

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

14. Oct 6, 2004

### Gokul43201

Staff Emeritus
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: Oct 6, 2004
15. Oct 7, 2004

### 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: Oct 7, 2004
16. Oct 7, 2004

### 3.14lwy

thank you :rofl: :rofl: :rofl: :rofl:

I will try the method.