Limitations of Induction Proofs (1 Viewer)

fettywap1738

New Member
Joined
Feb 24, 2018
Messages
6
Gender
Undisclosed
HSC
2019
What are the limitations of the method of proof by induction? i.e. What cant induction be used to solve?
 

sida1049

Well-Known Member
Joined
Jun 18, 2013
Messages
927
Gender
Male
HSC
2015
Proof by induction is almost worthless if you don't have a gist of what you're looking for.

Induction won't work for statements over uncountable sets. For example, induction might work for statements of the form S(k) where k is a natural number, but not when k can take arbitrary real numbers (or enumeration over other uncountable sets).

In order for proof by induction to work, it's typical that the statement you're trying to proof exhibits some kind of dependent structure. That is, you can expect the truth of S(k+1) to be contingent on S(k) being true. If what you're trying to proof lacks this sort of connection between S(k+1) and S(k), then don't expect induction to work.

I've stumbled across various examples of induction failing for the three issues I've mentioned, but I can't offer them off the top of my head, since I always find them by accident in the process of brainstorming an attack on a problem.
 

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top