Clarification on Proof by Contradiction

[Jonathanlikesmath]

Homework Statement

The product of any five consecutive integers is divisible by 120.

Relevant Equations

N/A

This is more a general question that this problem spurred and this is what I came up with. I do not feel it is acceptable but would like clarification moving forward.

My text states the format for proof by contradiction is as follow;
Proposition: P
PF: Suppose ~P.
...a little math and logic...
Therefore C ^ ~C.

Proposition: The product of any five consecutive integers is divisible by 120.

PF: Suppose for sake of contradiction the product of any five consecutive integers is not divisible by 120.

If we pick the first five integers, 1,2,3,4,5 we have 5! = 120.

And 120 divides the product of five consecutive integers and we have a contradiction.
Q.E.D.

So, what I did was state P, then negate it and produce a contradiction from that negation. But it honestly feels "cheesy" and I am not sure it is allowed.

Thanks
Jonathan

 

[Petek]

The proposition states that a certain property holds for any five consecutive integers. You have only shown that it holds for five specific integers. You need to generalize your argument.

 

[fresh_42]

Homework Statement:: The product of any five consecutive integers is divisible by 120.
Relevant Equations:: N/A

This is more a general question that this problem spurred and this is what I came up with. I do not feel it is acceptable but would like clarification moving forward.

My text states the format for proof by contradiction is as follow;
Proposition: P
PF: Suppose ~P.
...a little math and logic...
Therefore C ^ ~C.

Proposition: The product of any five consecutive integers is divisible by 120.

PF: Suppose for sake of contradiction the product of any five consecutive integers is not divisible by 120.

This is not the negation. It has to be: Suppose for sake of contradiction the product of some five consecutive integers is not divisible by 120.

If we pick the first five integers, 1,2,3,4,5 we have 5! = 120.

And here is why it is important. You can only assume that there are 5 consecutive integers, an existence, not a certain specification. So you have $120\,\nmid\,n(n+1)(n+2)(n+3)(n+4)$ for some integer $n$. Which one cannot be said.

And 120 divides the product of five consecutive integers and we have a contradiction.
Q.E.D.

So, what I did was state P, then negate it and produce a contradiction from that negation. But it honestly feels "cheesy" and I am not sure it is allowed.

Thanks
Jonathan

If you write or imagine logical symbols, then $\forall$ becomes $\exists$ by negation and vice versa.

Not all means there is.

 

[PeroK]

Homework Statement:: The product of any five consecutive integers is divisible by 120.
Relevant Equations:: N/A

This is more a general question that this problem spurred and this is what I came up with. I do not feel it is acceptable but would like clarification moving forward.

My text states the format for proof by contradiction is as follow;
Proposition: P
PF: Suppose ~P.
...a little math and logic...
Therefore C ^ ~C.

Proposition: The product of any five consecutive integers is divisible by 120.

PF: Suppose for sake of contradiction the product of any five consecutive integers is not divisible by 120.

If we pick the first five integers, 1,2,3,4,5 we have 5! = 120.

And 120 divides the product of five consecutive integers and we have a contradiction.
Q.E.D.

Proposition: The product of any five consecutive integers is 120.

Proof: Suppose for sake of contradiction the product of any five consecutive integers is not 120.

If we pick the first five integers, 1,2,3,4,5 we have 5! = 120. Contradiction. QED

So, what I did was state P, then negate it and produce a contradiction from that negation. But it honestly feels "cheesy" and I am not sure it is allowed.

"Cheesy" is putting it mildly!

 

[Office_Shredder]

In case an example helps to show the flaw.

Claim: every integer is equal to 1

Proof: suppose not every integer is equal to 1. Pick the first number. It's 1, hence a contradiction.

It's true that not every integer equals 1, but that doesn't mean no integer can equal one.

 

[WWGD]

Consider this:
120 is divisible by 8, 3, 5, and is the product of these.
You have:
n(n+1)(n+2)(n+3)(n+4).
Can you show the 3 factors will be contained in the product?
Hint:
Clearly one factor will be a multiple of 4. Now you need factors of 2,3,5.
Can you find them?

 

[Delta2]

Homework Statement:: The product of any five consecutive integers is divisible by 120.
Relevant Equations:: N/A

Proposition: The product of any five consecutive integers is divisible by 120.

PF: Suppose for sake of contradiction the product of any five consecutive integers is not divisible by 120.

Your mistake is right here when you are forming the negation of the proposition (NOT P,~P).

The logical negation of the proposition is "There exist five consecutive integers such that their product is not divisible by 120".

The negation isn't as you write that "The product of any five consecutive integers is not divisible by 120"

The general rule is that when you have a proposition in the form "For any ..., something holds" the negation is "There exist... such that "something" doesn't hold"..

 

[Jonathanlikesmath]

Your mistake is right here when you are forming the negation of the proposition (NOT P,~P).

The logical negation of the proposition is "There exist five consecutive integers such that their product is not divisible by 120".

The negation isn't as you write that "The product of any five consecutive integers is not divisible by 120"

The general rule is that when you have a proposition in the form "For any ..., something holds" the negation is "There exist... such that "something" doesn't hold"..

Ok, so I didn't negate the statement properly, I only negate part of the statement, qualifier needs to be negated as well.

 

[Jonathanlikesmath]

Consider this:
120 is divisible by 8, 3, 5, and is the product of these.
You have:
n(n+1)(n+2)(n+3)(n+4).
Can you show the 3 factors will be contained in the product?
Hint:
Clearly one factor will be a multiple of 4. Now you need factors of 2,3,5.
Can you find them?

Starting from 0 every fifth integer is a multiple of 5, every forth integer is a multiple of 4, every third is a multiple of 3 and every other is a multiple of 2. From this it follows that every set of five consecutive integers must contain a multiple of 5, a multiple of 4, at least one multiple of 3, and at least two multiples of.

 

[PeroK]

Starting from 0 every fifth integer is a multiple of 5, every forth integer is a multiple of 4, every third is a multiple of 3 and every other is a multiple of 2. From this it follows that every set of five consecutive integers must contain a multiple of 5, a multiple of 4, at least one multiple of 3, and at least two multiples of.

That's the basis of the proof. Can you formalise it more?

 

[PeroK]

Hint: a number is divisible by 120 if and only if it is divisible by all of 3, 5 and 8.

 

[Jonathanlikesmath]

Updated Proof.

Proposition: The product of any five consecutive integers is divisible by 120.

PF: Suppose for the sake of contradiction there exist five consecutive integers such that their product is not divisible by 120.

Consider the five consecutive integers n, (n-1), (n-2), (n-3), and (n-4), and the fact that ${n \choose 5}$ is an integer.

${n \choose 5} = \frac{n!}{(5!)(n-5!)} = \frac{(n)(n-1)(n-2)(n-3)(n-4)...(1)}{120(n-5)! } = \frac{(n)(n-1)(n-2)(n-3)(n-4)}{120}$

Thus we have a contradiction.

Q.E.D.

@PeroK I wrote this one while you posted, but I will also work one with the scheme that you quoted.

 

[PeroK]

Updated Proof.

Proposition: The product of any five consecutive integers is divisible by 120.

PF: Suppose for the sake of contradiction there exist five consecutive integers such that their product is not divisible by 120.

Consider the five consecutive integers n, (n-1), (n-2), (n-3), and (n-4), and the fact that ${n \choose 5}$ is an integer.

${n \choose 5} = \frac{n!}{(5!)(n-5!)} = \frac{(n)(n-1)(n-2)(n-3)(n-4)...(1)}{120(n-5)! } = \frac{(n)(n-1)(n-2)(n-3)(n-4)}{120}$

Thus we have a contradiction.

Q.E.D.

@PeroK I wrote this one while you posted, but I will also work one with the scheme that you quoted.

There's no need for a contradiction in that proof. You have a direct proof using binomial coefficients.

That said, the result for binomials, although a clever idea, is somewhat more advanced than the proposition in question.

 

[Jonathanlikesmath]

That's the basis of the proof. Can you formalise it more?

Proposition: The product of any five consecutive integers is divisible by 120.

PF: Suppose for the sake of contradiction that there exist five consecutive integers whose product is not divisible by 120.

Consider the sequence of integers starting from 0, every fifth integer is a multiple of 5, every fourth integer is a multiple of 4, every third a multiple of 3 and every other a multiple of two. So within this sequence of five consecutive integers its product will contain a factor of 5, 4, 3, and two factors of 2.

From this it follows that any set of five consecutive integers will also contain at a minimum a factor of 5, 4, 3, and at least two, possibly more, factors of 2. And it follows that the product of any five consecutive integers is a divisible by 5*4*3*2=120, which is a contradiction.

Q.E.D

 

[Delta2]

Consider the sequence of integers starting from 0, every fifth integer is a multiple of 5, every fourth integer is a multiple of 4, every third a multiple of 3 and every other a multiple of two. So within this sequence of five consecutive integers its product will contain a factor of 5, 4, 3, and two factors of 2.

Yes I think this is the main basic idea behind the proof of this problem, however to formalize it I think you need to use modulo arithmetic. You can prove that the product of five consecutive integers modulo 5, modulo 3 and modulo 2 and modulo 4 is zero.

 

[Jonathanlikesmath]

Yes I think this is the main basic idea behind the proof of this problem, however to formalize it I think you need to use modulo arithmetic. You can prove that the product of five consecutive integers modulo 5, modulo 3 and modulo 2 and modulo 4 is zero.

OK, I can see that being required to add some rigor. How do I know when I should add more details to formalize the proof or when I can proceed with a statement similar to "...it follows..."?

 

[Delta2]

OK, I can see that being required to add some rigor. How do I know when I should add more details to formalize the proof or when I can proceed with a statement similar to "...it follows..."?

Very good question but I don't have a very good answer. Sometimes an intuitive approach is good enough but sometimes you just have to add some formality and some rigor. In this case stating the main idea( that ever 5th integer is a multiple of 5, every 4th a multiple of 4th e.t.c )is not exactly the same as stating that in a random sample of 5 consecutive integers there will be a multiple of 5 , a multiple of 4 e.t.c. I know that one statement is consequence of the other but I think you got to prove exactly that it is a consequence.

 

[fresh_42]

OK, I can see that being required to add some rigor. How do I know when I should add more details to formalize the proof or when I can proceed with a statement similar to "...it follows..."?

A proof can be seen as a monologue to convince someone that a statement is true. Write it therefore as if it was written to convince yourself! Avoid cosmetic verbiage like "obvious", "clearly", or "easy to see". It once took me three days and four variable substitutions to "see" what the author described as an "obvious calculation". The same for conjunctions: "thus", "therefore", "implies", "follows", "hence", etc. If you cannot see that it is a "therefore" then your readers can't either.

When I check a proof, I always pay special attention to such phrases. They are the perfect place to hide a flaw!

 

[Jonathanlikesmath]

A proof can be seen as a monologue to convince someone that a statement is true. Write it therefore as if it was written to convince yourself! Avoid cosmetic verbiage like "obvious", "clearly", or "easy to see". It once took me three days and four variable substitutions to "see" what the author described as an "obvious calculation". The same for conjunctions: "thus", "therefore", "implies", "follows", "hence", etc. If you cannot see that it is a "therefore" then your readers can't either.

When I check a proof, I always pay special attention to such phrases. They are the perfect place to hide a flaw!

Done and done. Write it all out until somebody tells me that I am doing too much!

 

[PeroK]

OK, I can see that being required to add some rigor. How do I know when I should add more details to formalize the proof or when I can proceed with a statement similar to "...it follows..."?

The observation that I gave in the hint is one way to go. It's important to recognise that a number is divisible by 120 iff it is divisible by all of 3,5 and 8. Simply stating that and showing that you have those factors adds a lot to your proof.

For example, 60 has factors of 2,3,4 and 5 but is not divisible by 120. Being explicit about the factor of 8 is important.

 

[fresh_42]

Done and done. Write it all out until somebody tells me that I am doing too much!

I used to joke about "How to write a master thesis?" by saying: write it down so that you are convinced. Then delete all but every third line. (But keep them separately in case you need to explain something.)

However, this is an advanced procedure. Until then you have to exercise the whole text.

 

[Jonathanlikesmath]

The observation that I gave in the hint is one way to go. It's important to recognise that a number is divisible by 120 iff it is divisible by all of 3,5 and 8. Simply stating that and showing that you have those factors adds a lot to your proof.

For example, 60 has factors of 2,3,4 and 5 but is not divisible by 120. Being explicit about the factor of 8 is important.

I did not recognize that a number is divisible by 120 iff it is divisible by all of 3,5, and this statement is going to require some investigation on my part. Originally went the route binomial route because I instantly recognized 120=5!. I think my way forward is to complete more problems and I will start 'seeing' more things, I will go back to work out the proof again with mod arithmetic as @Delta2 suggested and attempt it as well using the IFF statement you provided.

 

[fresh_42]

I did not recognize that a number is divisible by 120 iff it is divisible by all of 3,5, and this statement is going to require some investigation on my part.

Indeed, since it is not obvious from the beginning. It only holds because $3,5,8$ are pairwise coprime. E.g. $12$ is divisible by $4$ and $6$ but not by $4\cdot 6 =24.$

So how does coprime play a role here? There are several methods to use it. The easiest is perhaps the factorization into powers of primes. Or you use theorems like Bézout's lemma.

 

[PeroK]

I did not recognize that a number is divisible by 120 iff it is divisible by all of 3,5, and this statement is going to require some investigation on my part. Originally went the route binomial route because I instantly recognized 120=5!. I think my way forward is to complete more problems and I will start 'seeing' more things, I will go back to work out the proof again with mod arithmetic as @Delta2 suggested and attempt it as well using the IFF statement you provided.

There are two aspects to any proof. Breaking down the proof into smaller pieces and then proving each of the smaller pieces.

At the very least I like to see an explanation of precisely what you are proving and why the proof holds together.

It's then clear to the reader what you are assuming. And the details can then be provided for any step that is not obvious.

Your binomial approach works well to show that the product of any $n$ consecutive positive integers is divisible by $n!$.

Whereas, the approach using prime factors looks harder to generalise.

 

[PeroK]

In terms of the general problem of showing that for any positive integers $n, k$ the product $(n+1)(n+2) \dots (n+k)$ is divisible by $k!$, I can't see a more direct way than using binomial coefficients:
$$(n+1)(n+2) \dots (n+k) = \binom{n+k}{k}k!$$The proof that all binomial coefficients are integers follows from induction using the identity:
$$\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$$Which holds for $0 < k < n+1$. The cases $k = 0, n+1$ are trivially the integer $1$. A proof of this is:
$$\binom{n}{k} + \binom{n}{k-1} = \frac{n!}{(n-k)!k!} + \frac{n!}{(n-k+1)!(k-1)!}$$$$ = \frac{n!}{(n-k)!(k-1)!}\bigg (\frac{1}{k} + \frac{1}{n-k+1} \bigg ) = \frac{n!}{(n-k)!(k-1)!}\bigg (\frac{n+1}{k(n-k+1)} \bigg )$$$$= \frac{(n+1)!}{(n-k+1)!k!} = \binom{n+1}{k}$$

 

[Jonathanlikesmath]

Indeed, since it is not obvious from the beginning. It only holds because $3,5,8$ are pairwise coprime. E.g. $12$ is divisible by $4$ and $6$ but not by $4\cdot 6 =24.$

So how does coprime play a role here? There are several methods to use it. The easiest is perhaps the factorization into powers of primes. Or you use theorems like Bézout's lemma.

Its amazing you mentioned Bezout's Lemma, even though its not named as such in my text, its highlighted as a "fundamental proposition" and proved as an exercise in the current section of my text!

 

[fresh_42]

Its amazing you mentioned Bezout's Lemma, even though its not named as such in my text, its highlighted as a "fundamental proposition" and proved as an exercise in the current section of my text!

What is also often useful is to use the real definition of a prime. Prime numbers are usually (at school) defined as irreducible numbers: no other divisors than itself and $\pm 1.$ But this is irreducibility, not primality. A number is prime if it is no unit ($\neq \pm 1$) and if $p\,|\,a\cdot b \Longrightarrow p\,|\,a \text{ or }p\,|\,b\,.$ If it divides a product, then it divides already a factor. That both terms are equivalent for integers is a theorem. So strictly speaking: the school definition is the wrong definition.

 

[Jonathanlikesmath]

Yes I think this is the main basic idea behind the proof of this problem, however to formalize it I think you need to use modulo arithmetic. You can prove that the product of five consecutive integers modulo 5, modulo 3 and modulo 2 and modulo 4 is zero.

I was working this and was thinking something along the lines of this for the modulo arithmetic. I got to a point where I need to use induction, so I might have taken a wrong turn... And have removed some things such as the first paragraph covering how the factors are spread across the first five integers.

Proposition: The product of any five consecutive integers is divisible by 120.

PF:
Let the integer P be the product of five consecutive integers n, n-1, n-2, n-3, and n-4.

To show that the integer P is divisible by 120 we must show that P is divisible by 3,5, and 8 by showing that P is congruent to 0 (mod 3), (mod 5), and (mod 8). P $\equiv 0 (mod 5) \Rightarrow 5 | P - 0 \Rightarrow 5 | P$

Note, P = (n)(n+1)(n+2)(n+3)(n+4) = $n^5 + 10n^4 +35n^3 + 50n^2 + 24n$

Substituting the value for P we have, $5 | n^5 + 10n^4 +35n^3 + 50n^2 + 24n$

$5 | (n^5 + 24n) + 5(2n^4 + 7n^3 +10n^2)$

The second part of the RHS is divisible by 5, so now we need to focus on $(n^5 + 24n)$.

*/ Note to forum, I couldn't get $(n^5 + 24n)$ into a form algebraically that shows it is divisible by 5, but it "is" (my previous proofs would imply this?) so I have decided to use induction but I was having an issue but I believe I resolved it below/*

Note: Induction is typically for the natural numbers; while we are working with the integers. In this case we can use induction and it will also cover the negative integers as well. This is because any negative integer raised to the fifth power is negative and then we would be adding a negative 24 * n value, resulting in a negative sum. This sum has the same magnitude as the positive integer value, just with a negative sign.

Show $5 | (n^5 + 24n)$.

Let n = 1, then $5 | (1^5 + 24(1)) = 25,$ is true.

Assume n = k such that $5 | (k^5 + 24k)$ is true and $(k^5 + 24k) = 5c$, for some integer c.

We want to show that n = k + 1 is true.

$(k+1)^5 + 24(k+1) = k^5 + 5k^4 + 10k^3 + 10k^2 + 29k + 25$.

$= (k^5 + 24k) + 5k^4 + 10k^3 + 10k^2 + 5k + 25$.

$= 5c + 5k^4 + 10k^3 + 10k^2 + 5k + 25$.

$= 5[c + k^4 + 2k^3 + 2k^2 + k + 5]$.

Therefor $5 | (k+1)^5 + 24(k+1)$.

So we now see that $P \equiv 0 (mod 5)$ which shows 5 is a factor of any set of five consecutive integers.Ok, that was a lot more than I thought it would be and it still needs to be done twice more to complete the entire proof.

 

[PeroK]

A better approach if you want to use modular arithmetic is to take:
$$P = (n - 2)(n-1)n(n+1)(n+2) = n(n^2 -1)(n^2 - 4)$$If $n$ is not divisible by $3$, then $n = 1$ or $2 \ (mod \ 3)$; $n^2 = 1 \ (mod \ 3)$, so $n^2 -1$ is divisible by $3$. Etc.

 

[Office_Shredder]

I think it's sufficiently rigorous to just observe that 5 must divide one of five consecutive integers. Similar for 3. 8 is the tricky one, but you can show there are two even numbers, and one of them is divisible by 4.

 

[Delta2]

@Jonathanlikesmath now you are very rigorous but you did it the very hard way, I had in mind something like what @PeroK suggests at post #29.

More specifically, if we write the product as $n(n+1)(n+2)(n+3)(n+4)$ then it will be either $n\pmod 5=0$ in which case we are finished, or one of the cases of $n\pmod 5=1,n\pmod 5=2,n\pmod 5=3,n\pmod 5=4$. If for example $n\pmod 5=1$ then $(n+4)\pmod 5=n\pmod 5+4\pmod 5=1+4\pmod 5=5\pmod 5 =0$, hence in this case 5 divides n+4. Similarly we can handle the other cases.

 

[Jonathanlikesmath]

@Jonathanlikesmath now you are very rigorous but you did it the very hard way, I had in mind something like what @PeroK suggests at post #29.

More specifically, if we write the product as $n(n+1)(n+2)(n+3)(n+4)$ then it will be either $n\pmod 5=0$ in which case we are finished, or one of the cases of $n\pmod 5=1,n\pmod 5=2,n\pmod 5=3,n\pmod 5=4$. If for example $n\pmod 5=1$ then $(n+4)\pmod 5=n\pmod 5+4\pmod 5=1+4\pmod 5=5\pmod 5 =0$, hence in this case 5 divides n+4. Similarly we can handle the other cases.

Well, I soon won't forget this method. Thank you all for the help!

 

[PeroK]

A better approach if you want to use modular arithmetic is to take:
$$P = (n - 2)(n-1)n(n+1)(n+2) = n(n^2 -1)(n^2 - 4)$$If $n$ is not divisible by $3$, then $n = 1$ or $2 \ (mod \ 3)$; $n^2 = 1 \ (mod \ 3)$, so $n^2 -1$ is divisible by $3$. Etc.

Just to say that I thought reducing the product to three terms looked like a good idea (and it is always something to consider), but in this case it doesn't really help. @Delta2 's method is much simpler!