Matematička indukcija

#fax #math #ds1 [deo poglavlja "prirodni brojevi"]

Sledeći principi su ekvivalentni.

Princip matematičke indukcije (P5.)

Neka je svojstvo prirodnih brojeva takvo da

  • važi
  • za svaki prirodni broj ako važi onda važi i

tada važi za svaki prirodni broj .

Princip potpune indukcije

Neka je svojstvo prirodnih brojeva takvo da

  • za svaki prirodni broj ako važi onda važi i

tada važi za svaki prirodni broj .

Teorema. PMI PPI

Princip najmanjih elemenata

Neka je tada u postoji najmanji element.

Teorema. PPI PNE

Još varijacije matematičke indukcije

  1. Neka je svojstvo prirodnih brojeva takvo da

    • važi za neko
    • za svaki prirodni broj ako važi onda važi i

    tada važi za svaki prirodni broj .

  2. Neka je svojstvo prirodnih brojeva takvo da

    • važe za neko
    • za svaki prirodni broj ako važe onda važi i

    tada važi za svaki prirodni broj .