Can you use proof by contradiction in the midst of induction

Click For Summary

Discussion Overview

The discussion revolves around the use of proof by contradiction within the framework of mathematical induction. Participants explore whether it is valid to assume that if P(k) holds, then P(k+1) must also hold by assuming the opposite (that P(k+1) does not hold) and deriving a contradiction. The context includes theoretical considerations and examples related to proving inequalities involving squared terms.

Discussion Character

  • Exploratory
  • Technical explanation
  • Conceptual clarification
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant questions whether it is acceptable to use contradiction in an inductive proof, specifically by assuming P(k) holds and P(k+1) does not, to derive a contradiction.
  • Another participant confirms that using contradiction in this manner is valid, citing logical equivalence and inference rules such as Reductio Ad Absurdam and Conditional Proof.
  • A participant emphasizes the importance of properly proving the contrary to be impossible rather than simply disproving one counter-example when using contradiction.
  • Further clarification is provided regarding the necessity of proving the antecedent in the context of the example involving squared terms, suggesting that the assumption itself suffices.
  • One participant reflects on their understanding of induction and expresses appreciation for being able to articulate their proof strategy clearly.
  • A later reply suggests a minor adjustment to the phrasing of the proof to explicitly state that it is a proof by contradiction.
  • Another participant recognizes their example as a proof of the non-negativity of the dot product of a vector with itself.

Areas of Agreement / Disagreement

Participants generally agree that using proof by contradiction within induction is valid, though there are nuances in how it should be articulated and applied. Some uncertainty remains regarding the specifics of proof structure and the handling of assumptions.

Contextual Notes

Participants express varying levels of confidence in their understanding of induction and proof techniques, indicating that some foundational concepts may still be developing. There is also mention of potential limitations in the example provided, particularly regarding the assumptions made about squared terms.

Who May Find This Useful

This discussion may be useful for students and practitioners of mathematics who are learning about proof techniques, particularly induction and contradiction, as well as those interested in the properties of inequalities and mathematical reasoning.

Battlemage!
Messages
292
Reaction score
44
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
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   Reactions: Battlemage!
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."
 
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.
 

Similar threads

Undergrad Understanding extinction probability in simple GWP
  • · Replies 1 ·
Replies
1
Views
3K
Body forces in static equilibrium (FEM issue)
  • · Replies 2 ·
Replies
2
Views
2K
High School Confusion when considering pV=nRT in Two Balloon experiment
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad Can you make the induction step by contradiction?
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Question about mathematical induction
  • · Replies 10 ·
Replies
10
Views
2K
Undergrad Understanding permutations and combinations in a coin toss experiment
  • · Replies 6 ·
Replies
6
Views
2K
Undergrad Ways to put n balls in m boxes such that exactly k boxes are empty?
  • · Replies 29 ·
Replies
29
Views
6K
Undergrad The set of nonzero values of pmf is at most countable
  • · Replies 3 ·
Replies
3
Views
4K
MHB Sequence of b_{k} with Explicit Formula: Proving by Math Induction
  • · Replies 2 ·
Replies
2
Views
1K
Undergrad Prove that the tail of this distribution goes to zero
  • · Replies 2 ·
Replies
2
Views
2K