Prove by Mathematical induction , please help

  • Mathematica
  • Thread starter 3.14lwy
  • Start date
  • #1
15
0

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

it is in urgent , please help , thank you! :smile:
 

Answers and Replies

  • #2
uart
Science Advisor
2,776
9
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
695
0
But 3! is 6.
 
  • #4
matt grime
Science Advisor
Homework Helper
9,395
3
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
uart
Science Advisor
2,776
9
matt grime said:
isn't the *product* of 3 consecutive integers
Doh silly mistake, I read it as sum instead of product.
 
  • #6
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
131
Don't be ashamed, uart; I made a much sillier mistake..
 
  • #7
uart
Science Advisor
2,776
9
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:
  • #8
136
0
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
Tide
Science Advisor
Homework Helper
3,076
0
In a sequence of n consecutive integers, there must be at least one number divisible by j where j <= n.
 
  • #10
15
0
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

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:
  • #11
644
1
::
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
15
0
TenaliRaman you are right ,

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

I can't finish it by M.I. :frown:
 
  • #13
uart
Science Advisor
2,776
9
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.
 
  • #14
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
17
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:
  • #15
uart
Science Advisor
2,776
9
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:
  • #16
15
0
thank you :rofl: :rofl: :rofl: :rofl:

I will try the method. :smile:
 

Related Threads for: Prove by Mathematical induction , please help

Replies
8
Views
2K
Replies
11
Views
2K
Replies
3
Views
20K
Replies
5
Views
7K
Replies
8
Views
3K
Replies
3
Views
30K
Replies
14
Views
4K
Top