# Thread: Limitations of Induction Proofs

1. ## Limitations of Induction Proofs

What are the limitations of the method of proof by induction? i.e. What cant induction be used to solve?

2. ## Re: Limitations of Induction Proofs

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.

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•