Mathematica Prove by Mathematical induction ,

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

 

[uart]

You can't 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!

 

[Muzza]

But 3! is 6.

 

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

 

[uart]

isn't the *product* of 3 consecutive integers

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

 

[arildno]

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

 

[uart]

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.

 

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

 

[Tide]

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

 

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

 

[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!
[/Color]::

 

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

 

[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]

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.

 

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

 

[3.14lwy]

thank you

I will try the method.