Can you make the induction step by contradiction?

  • #1
314
122

Main Question or Discussion Point

Assuming you've sufficiently proven your inductive basis, can you complete a proof by induction in the following manner:

Make the inductive hypothesis, assume P(n) is true for some n. Assume P(n+1) is not true. If it follows from the assumption that P(n+1) is false that P(n) must also therefore be false, contradicting the inductive hypothesis, does this mean P(n) must imply P(n+1)?
 

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,792
1,390
Yes, that is valid.
The assumption from which you derived the contradiction was ##\exists n\ P(n)\wedge\neg P(n+1)##. Deriving a contradiction from this proves its negation, which is ##\forall n\neg(P(n)\wedge \neg P(n+1))##
which, by de Morgan, is equivalent to
##\forall n\ \neg P(n)\vee P(n+1)##
which is equivalent to
##\forall n\ P(n)\to P(n+1)##
which is what we need to complete the induction.
 
  • #3
314
122
Lovely, thank you :)
 

Related Threads on Can you make the induction step by contradiction?

  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
4
Views
8K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
2
Views
3K
Replies
4
Views
2K
  • Last Post
Replies
5
Views
5K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
1K
Top