Insights Blog
-- Browse All Articles --
Physics Articles
Physics Tutorials
Physics Guides
Physics FAQ
Math Articles
Math Tutorials
Math Guides
Math FAQ
Education Articles
Education Guides
Bio/Chem Articles
Technology Guides
Computer Science Tutorials
Forums
General Math
Calculus
Differential Equations
Topology and Analysis
Linear and Abstract Algebra
Differential Geometry
Set Theory, Logic, Probability, Statistics
MATLAB, Maple, Mathematica, LaTeX
Trending
Featured Threads
Log in
Register
What's new
Search
Search
Search titles only
By:
General Math
Calculus
Differential Equations
Topology and Analysis
Linear and Abstract Algebra
Differential Geometry
Set Theory, Logic, Probability, Statistics
MATLAB, Maple, Mathematica, LaTeX
Menu
Log in
Register
Navigation
More options
Contact us
Close Menu
JavaScript is disabled. For a better experience, please enable JavaScript in your browser before proceeding.
You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an
alternative browser
.
Forums
Mathematics
Set Theory, Logic, Probability, Statistics
Can you use proof by contradiction in the midst of induction
Reply to thread
Message
[QUOTE="Battlemage!, post: 5416427, member: 135434"] 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 [I]not[/I], 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 (u[SUB]1[/SUB])[SUP]2[/SUP], (u[SUB]2[/SUB])[SUP]2[/SUP], ..., (u[SUB]n[/SUB])[SUP]2[/SUP] are all each ≥ 0 for u[SUB]1[/SUB], u[SUB]2[/SUB], ... u[SUB]n[/SUB] in R, then the sum (u[SUB]1[/SUB])[SUP]2[/SUP]+ (u[SUB]2[/SUB])[SUP]2[/SUP]+ ...+ (u[SUB]n[/SUB])[SUP]2[/SUP] ≥ 0. Well, clearly (u[SUB]1[/SUB])[SUP]2[/SUP] and (u[SUB]2[/SUB])[SUP]2[/SUP] are each ≥ 0 by the rules of squared numbers in R, so it's clear that (u[SUB]1[/SUB])[SUP]2[/SUP]+ (u[SUB]2[/SUB])[SUP]2[/SUP] ≥ 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 (u[SUB]1[/SUB])[SUP]2[/SUP]+ (u[SUB]2[/SUB])[SUP]2[/SUP]+ ...+ (u[SUB]k[/SUB])[SUP]2[/SUP] ≥ 0 and use that to show that it therefore follows that (u[SUB]1[/SUB])[SUP]2[/SUP]+ (u[SUB]2[/SUB])[SUP]2[/SUP]+ ...+ (u[SUB]k[/SUB])[SUP]2[/SUP] + (u[SUB]k+1[/SUB])[SUP]2[/SUP] ≥ 0. Can I instead assume that (u[SUB]1[/SUB])[SUP]2[/SUP]+ (u[SUB]2[/SUB])[SUP]2[/SUP]+ ...+ (u[SUB]k[/SUB])[SUP]2[/SUP] ≥ 0 AND assume that (u[SUB]1[/SUB])[SUP]2[/SUP]+ (u[SUB]2[/SUB])[SUP]2[/SUP]+ ...+ (u[SUB]k[/SUB])[SUP]2[/SUP] + (u[SUB]k+1[/SUB])[SUP]2[/SUP] [B]<[/B] 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 (u[SUB]1[/SUB])[SUP]2[/SUP]+ (u[SUB]2[/SUB])[SUP]2[/SUP]+ ...+ (u[SUB]k[/SUB])[SUP]2[/SUP] ≥ 0 holds and that (u[SUB]1[/SUB])[SUP]2[/SUP]+ (u[SUB]2[/SUB])[SUP]2[/SUP]+ ...+ (u[SUB]k[/SUB])[SUP]2[/SUP] + (u[SUB]k+1[/SUB])[SUP]2[/SUP] < 0. Then that would mean that (u[SUB]1[/SUB])[SUP]2[/SUP]+ (u[SUB]2[/SUB])[SUP]2[/SUP]+ ...+ (u[SUB]k[/SUB])[SUP]2[/SUP] < -(u[SUB]k+1[/SUB])[SUP]2[/SUP]. By the same reasoning I would have used to show that (u[SUB]1[/SUB])[SUP]2[/SUP] and (u[SUB]2[/SUB])[SUP]2[/SUP] ≥ 0, I would show that (u[SUB]k+1[/SUB])[SUP]2[/SUP] ≥ 0, which would make - (u[SUB]k+1[/SUB])[SUP]2[/SUP] < 0, but that would mean that (u[SUB]1[/SUB])[SUP]2[/SUP]+ (u[SUB]2[/SUB])[SUP]2[/SUP]+ ...+ (u[SUB]k[/SUB])[SUP]2[/SUP] < 0, which would contradiction my assumption that (u[SUB]1[/SUB])[SUP]2[/SUP]+ (u[SUB]2[/SUB])[SUP]2[/SUP]+ ...+ (u[SUB]k[/SUB])[SUP]2[/SUP] ≥ 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. [/QUOTE]
Insert quotes…
Post reply
Forums
Mathematics
Set Theory, Logic, Probability, Statistics
Can you use proof by contradiction in the midst of induction
Back
Top