Clarification on Proof by Contradiction

In summary: To negate "For any ..., something does not hold" you need to write "There exists some ... such that ... does not hold".In summary, this is what I came up with. I do not feel it is acceptable but would like clarification moving forward.
  • #1
Jonathanlikesmath
17
15
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
 
Physics news on Phys.org
  • #2
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.
 
  • Like
Likes SammyS
  • #3
Jonathanlikesmath said:
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.
Jonathanlikesmath said:
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.
Jonathanlikesmath 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.
 
  • Like
Likes Jonathanlikesmath
  • #4
Jonathanlikesmath said:
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
Jonathanlikesmath said:
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!
 
  • Haha
Likes Jonathanlikesmath
  • #5
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.
 
  • Like
Likes phinds and PeroK
  • #6
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?
 
  • #7
Jonathanlikesmath said:
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"..
 
Last edited:
  • #8
Delta2 said:
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.
 
  • Like
Likes fresh_42
  • #9
WWGD said:
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.
 
  • Like
Likes WWGD
  • #10
Jonathanlikesmath said:
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?
 
  • #11
Hint: a number is divisible by 120 if and only if it is divisible by all of 3, 5 and 8.
 
  • #12
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.
 
  • Like
Likes Delta2
  • #13
Jonathanlikesmath said:
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.
 
  • Like
Likes Jonathanlikesmath
  • #14
PeroK said:
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
 
  • Like
  • Informative
Likes WWGD and Delta2
  • #15
Jonathanlikesmath said:
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.
 
  • #16
Delta2 said:
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..."?
 
  • Like
Likes Delta2
  • #17
Jonathanlikesmath said:
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.
 
  • Like
Likes Jonathanlikesmath
  • #18
Jonathanlikesmath said:
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!
 
  • Like
Likes Delta2
  • #19
fresh_42 said:
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!
 
  • Like
Likes Delta2
  • #20
Jonathanlikesmath said:
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.
 
  • #21
Jonathanlikesmath said:
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.
 
  • Haha
Likes Jonathanlikesmath
  • #22
PeroK said:
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.
 
  • Like
Likes Delta2
  • #23
Jonathanlikesmath said:
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.
 
  • Informative
Likes Delta2
  • #24
Jonathanlikesmath said:
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.
 
  • Informative
Likes Delta2
  • #25
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}$$
 
  • #26
fresh_42 said:
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!
 
  • #27
Jonathanlikesmath said:
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.
 
  • #28
Delta2 said:
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.
 
  • Like
Likes Delta2
  • #29
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.
 
  • Like
Likes Delta2
  • #30
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.
 
  • Like
Likes fresh_42
  • #31
@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.
 
Last edited:
  • Like
Likes PeroK
  • #32
Delta2 said:
@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!
 
  • Like
Likes Delta2
  • #33
PeroK said:
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!
 
  • Like
Likes Delta2

FAQ: Clarification on Proof by Contradiction

1. What is the concept of proof by contradiction?

Proof by contradiction is a mathematical proof technique that involves assuming the opposite of what you are trying to prove and then showing that this leads to a contradiction or an impossible situation. This contradiction then proves that the original assumption must be true.

2. How is proof by contradiction different from other proof techniques?

Proof by contradiction is different from other proof techniques because it relies on a logical contradiction rather than directly proving something to be true. It is often used when a direct proof is difficult or impossible to construct.

3. What are the steps involved in a proof by contradiction?

The first step in a proof by contradiction is to assume the opposite of what you are trying to prove. Then, using deductive reasoning and logical steps, you must show that this assumption leads to a contradiction. This contradiction then proves that the original assumption must be true. Finally, you must state your conclusion and provide a logical explanation of how the contradiction proves it.

4. Can proof by contradiction be used in all mathematical proofs?

No, proof by contradiction cannot be used in all mathematical proofs. It is most commonly used in proofs involving logic, number theory, and geometry. It is not suitable for proofs in other branches of mathematics, such as calculus or linear algebra.

5. Are there any drawbacks to using proof by contradiction?

One potential drawback of proof by contradiction is that it does not provide a direct explanation or understanding of why something is true. It only shows that the opposite cannot be true. Additionally, it can be a more complex and time-consuming proof technique compared to other methods.

Back
Top