Prove by Mathematical induction ,

In summary, In summary, 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! But 3! is 6. but 33 isn't divisble by 3!, however, since 33 isn't the *product* of 3 consecutive integers, that's neither here nor there. isn't the *product* of 3 consecutive integers.
  • #1
3.14lwy
15
0
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:
 
Physics news on Phys.org
  • #2
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!
 
  • #3
But 3! is 6.
 
  • #4
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
matt grime said:
isn't the *product* of 3 consecutive integers

Doh silly mistake, I read it as sum instead of product.
 
  • #6
Don't be ashamed, uart; I made a much sillier mistake..
 
  • #7
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
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
In a sequence of n consecutive integers, there must be at least one number divisible by j where j <= n.
 
  • #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

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

I will try the method. :smile:
 

1. What is mathematical induction?

Mathematical induction is a proof technique used to show that a statement is true for all natural numbers. It involves proving a base case and then showing that if the statement is true for one natural number, it is also true for the next consecutive number. This process is repeated until the statement is shown to be true for all natural numbers.

2. Why is mathematical induction important?

Mathematical induction is important because it allows us to prove statements about infinite sets, such as the set of natural numbers. It is also a fundamental tool in higher level mathematics and is used to prove theorems and solve problems in various branches of mathematics.

3. What is the difference between strong and weak induction?

In strong induction, we use the fact that the statement is true for all previous natural numbers to prove that it is true for the next consecutive number. In weak induction, we only use the fact that the statement is true for the previous number to prove that it is true for the next consecutive number. Strong induction is more powerful than weak induction and can be used in cases where weak induction cannot.

4. Can mathematical induction be used to prove any statement?

No, mathematical induction can only be used to prove statements that are true for all natural numbers. It cannot be used to prove statements that are only true for a specific set of numbers or for statements involving real numbers or other types of numbers.

5. What are some common mistakes to avoid when using mathematical induction?

Some common mistakes to avoid when using mathematical induction include assuming that the statement is true for all natural numbers without proving it, using incorrect or incomplete base cases, and using circular reasoning. It is important to carefully and logically follow each step of the induction process to ensure a valid proof.

Similar threads

  • Calculus and Beyond Homework Help
Replies
6
Views
869
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
971
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
3K
  • Programming and Computer Science
Replies
8
Views
200
  • Calculus and Beyond Homework Help
Replies
4
Views
986
Replies
5
Views
2K
Replies
2
Views
313
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Electromagnetism
Replies
16
Views
989
Back
Top