Results 1 to 2 of 2

Thread: Limitations of Induction Proofs

  1. #1
    New Member
    Join Date
    Feb 2018
    Rep Power

    Exclamation 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. #2
    Senior Member sida1049's Avatar
    Join Date
    Jun 2013
    Rep Power

    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.

    Bachelor of Science (Advanced Mathematics) III, USYD

Thread Information

Users Browsing this Thread

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