Can you use proof by contradiction in the midst of induction

In summary: Essentially what I'd be doing is instead of directly showing that if P(k) holds then P(k+1) holds, I'd be showing that if P(k) holds and (u1)2+ (u2)2+ ...+ (uk)2 does not hold that a contradiction is reached, and therefore if P(k) holds then P(k+1) holds).So it would look like this:Assume that (u1)2+ (u2)2+ ...+ (uk)2 ≥ 0 holds and that (u1)2+ (u2)2+ ...+ (uk)2 + (uk+1)2 < 0.
  • #1
Battlemage!
294
45
In the process of doing a proof by induction, can you use a contradiction to show that if P(k) holds then P(k+1) must hold? What I mean is, after establishing that P(0) holds, can I assume that P(k) holds and that P(k+1) does not, and show that a contradiction arises, and thus conclude that if P(k) holds then P(k+1) must also hold? If I can, then in combination with showing that P(0) holds, then the proof for induction would be complete if I understand the process.

Let me give an example.

Say I wanted to prove that if (u1)2, (u2)2, ..., (un)2 are all each ≥ 0 for u1, u2, ... un in R,
then the sum (u1)2+ (u2)2+ ...+ (un)2 ≥ 0.

Well, clearly (u1)2 and (u2)2 are each ≥ 0 by the rules of squared numbers in R, so it's clear that (u1)2+ (u2)2 ≥ 0. So let's say I have shown that (I'm sure to actually prove it I'd have to get into some basic axioms, but let's just pretend that has been done).

Usually in an inductive proof, if I understand it correctly, the next step would be to assume that
(u1)2+ (u2)2+ ...+ (uk)2 ≥ 0 and use that to show that it therefore follows that (u1)2+ (u2)2+ ...+ (uk)2 + (uk+1)2 ≥ 0.
Can I instead assume that (u1)2+ (u2)2+ ...+ (uk)2 ≥ 0 AND assume that (u1)2+ (u2)2+ ...+ (uk)2 + (uk+1)2 < 0,
and show that I arrive at a contradiction, thereby proving that P(k) => P(k+1)? (Essentially what I'd be doing is instead of directly showing that if P(k) holds then P(k+1) holds, I'd be showing that if P(k) holds and P(k+1) does not hold that a contradiction is reached, and therefore if P(k) holds then P(k+1) holds).

So it would look like this:
Assume that (u1)2+ (u2)2+ ...+ (uk)2 ≥ 0 holds and that (u1)2+ (u2)2+ ...+ (uk)2 + (uk+1)2 < 0.

Then that would mean that
(u1)2+ (u2)2+ ...+ (uk)2 < -(uk+1)2.
By the same reasoning I would have used to show that (u1)2 and (u2)2 ≥ 0, I would show that (uk+1)2 ≥ 0, which would make - (uk+1)2 < 0, but that would mean that (u1)2+ (u2)2+ ...+ (uk)2 < 0, which would contradiction my assumption that (u1)2+ (u2)2+ ...+ (uk)2 ≥ 0. By contradiction, it would have to mean that the case for P(k+1) holds.

Granted, this proof outline itself is garbage and more or less ignores that a number times itself is positive in R, but I'm more worried about the principle itself. After showing P(0) is true, can we show that if P(k) holds then P(k+1) holds by assuming it does NOT and then arriving at a contradiction?

Also, if you want to critique/correct my "fake" proof please do. Thanks and sorry for this weird and all over the place question.
 
Physics news on Phys.org
  • #2
Yes you can do that.
##P(k)\wedge \neg P(k+1)\Rightarrow \bot## is logically equivalent to ##P(k)\Rightarrow P(k+1)##, by the use of the inference rules
- Reductio Ad Absurdam (RAA); and
- Conditional Proof (CP)

which you can see in this list of inference rules.
 
  • Like
Likes Battlemage!
  • #3
Battlemage! said:
In the process of doing a proof by induction, can you use a contradiction to show that if P(k) holds then P(k+1) must hold? What I mean is, after establishing that P(0) holds, can I assume that P(k) holds and that P(k+1) does not, and show that a contradiction arises, and thus conclude that if P(k) holds then P(k+1) must also hold? If I can, then in combination with showing that P(0) holds, then the proof for induction would be complete if I understand the process.
Sure. The law of contradiction is fundamental. So long as you are using it properly (for instance, you must actually prove the contrary to be impossible, not disprove one counter-example) then you're good to go.

Battlemage! said:
Say I wanted to prove that if (u1)2, (u2)2, ..., (un)2 are all each ≥ 0 for u1, u2, ... un in R,
then the sum (u1)2+ (u2)2+ ...+ (un)2 ≥ 0.

Well, clearly (u1)2 and (u2)2 are each ≥ 0 by the rules of squared numbers in R, so it's clear that (u1)2+ (u2)2 ≥ 0. So let's say I have shown that (I'm sure to actually prove it I'd have to get into some basic axioms, but let's just pretend that has been done).
You don't need the rules of squared numbers in R, we get that fact simply from your assumption. You don't need to prove your antecedent true.

Battlemage! said:
Usually in an inductive proof, if I understand it correctly, the next step would be to assume that
(u1)2+ (u2)2+ ...+ (uk)2 ≥ 0 and use that to show that it therefore follows that (u1)2+ (u2)2+ ...+ (uk)2 + (uk+1)2 ≥ 0.
Can I instead assume that (u1)2+ (u2)2+ ...+ (uk)2 ≥ 0 AND assume that (u1)2+ (u2)2+ ...+ (uk)2 + (uk+1)2 < 0,
and show that I arrive at a contradiction, thereby proving that P(k) => P(k+1)? (Essentially what I'd be doing is instead of directly showing that if P(k) holds then P(k+1) holds, I'd be showing that if P(k) holds and P(k+1) does not hold that a contradiction is reached, and therefore if P(k) holds then P(k+1) holds).

So it would look like this:
Assume that (u1)2+ (u2)2+ ...+ (uk)2 ≥ 0 holds and that (u1)2+ (u2)2+ ...+ (uk)2 + (uk+1)2 < 0.

Then that would mean that
(u1)2+ (u2)2+ ...+ (uk)2 < -(uk+1)2.
By the same reasoning I would have used to show that (u1)2 and (u2)2 ≥ 0, I would show that (uk+1)2 ≥ 0, which would make - (uk+1)2 < 0, but that would mean that (u1)2+ (u2)2+ ...+ (uk)2 < 0, which would contradiction my assumption that (u1)2+ (u2)2+ ...+ (uk)2 ≥ 0. By contradiction, it would have to mean that the case for P(k+1) holds.

Granted, this proof outline itself is garbage and more or less ignores that a number times itself is positive in R, but I'm more worried about the principle itself. After showing P(0) is true, can we show that if P(k) holds then P(k+1) holds by assuming it does NOT and then arriving at a contradiction?

Also, if you want to critique/correct my "fake" proof please do. Thanks and sorry for this weird and all over the place question.

This all looks great. Well done. Only thing I would suggest you change (and its a minor detail) is to specify that you are doing a proof by contradiction in your declarative statement. Instead of saying "Assume that (u1)2+ (u2)2+ ...+ (uk)2 ≥ 0 holds and that (u1)2+ (u2)2+ ...+ (uk)2 + (uk+1)2 < 0." say "Assume by way of contradiction that (u1)2+ (u2)2+ ...+ (uk)2 ≥ 0 holds and that (u1)2+ (u2)2+ ...+ (uk)2 + (uk+1)2 < 0."
 
  • #4
Thanks for the responses. I was a little iffy on that probably because induction isn't my strong suit. Also I am glad to know I can state exactly what I'm doing without losing the proper language of a proof (something I am definitely still learning).

Incidentally I just realized my "test proof" is a proof that the dot product of a vector u and itself is always greater than or equal to zero. Because obviously each component times itself and then summed up over all all the indices would look exactly like the above.

Thanks again. Any more info is always appreciated.
 

1. Can proof by contradiction be used in the midst of induction?

Yes, proof by contradiction can be used in the midst of induction. In fact, it is a common approach used in mathematical proofs to show that a statement or theorem holds for all cases.

2. How does proof by contradiction work in the midst of induction?

In proof by contradiction, we assume that the statement we are trying to prove is false and then show that this leads to a contradiction. This contradiction then proves that our initial assumption must be false, and therefore the statement is true.

3. Why is proof by contradiction useful in the midst of induction?

Proof by contradiction is useful in induction because it allows us to prove a statement for all cases by only considering a single case. This can save time and effort in proving a statement that holds for an infinite number of cases.

4. Are there any limitations to using proof by contradiction in the midst of induction?

There are some limitations to using proof by contradiction in induction. This approach may not always work for every statement and can sometimes lead to circular reasoning. It is important to carefully consider the assumptions made and ensure they do not contradict the statement being proven.

5. Can proof by contradiction be used in other types of proofs besides induction?

Yes, proof by contradiction can be used in other types of proofs besides induction. It is a common approach in mathematical and scientific proofs to show that a statement holds for all cases. However, it may not be the most efficient or appropriate approach for every proof.

Similar threads

Body forces in static equilibrium (FEM issue)
    • Mechanical Engineering
Replies
2
Views
1K
B Confusion when considering pV=nRT in Two Balloon experiment
    • Classical Physics
Replies
7
Views
845
Geometric Sequence and the Limiting Value
    • Precalculus Mathematics Homework Help
Replies
4
Views
1K
A Runners in a race, probability paradox
    • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
Using ODE45 on Matlab to Integrate A Problem
    • Engineering and Comp Sci Homework Help
Replies
1
Views
894
I Prove that the tail of this distribution goes to zero
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
I Question about about halting problem and this particular function
    • Set Theory, Logic, Probability, Statistics
2
Replies
54
Views
4K
I Is an algorithm for a proof required to halt?
    • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
MHB Sequence of b_{k} with Explicit Formula: Proving by Math Induction
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
933
MHB How Can the 4 Rod Tower of Hanoi Inequality Be Solved?
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
888

Hot Threads

Recent Insights

Back
Top