Sedno indukcji

[psi]

Cześć!
Ciężko idzie mi ze zrozumieniem sedna dowodu indukcyjnego. Odtwarzam go mechanicznie ale w ogóle nie czuję. Coś mi się kołacze po głowie ale ciągle mnie to gryzie. Otóż sprawdzam pierwszy warunek dla n=1 czy badany wzór jest prawdziwy. I to jest jasne. Natomiast największy problem dla mnie to krok drugi, a konkretnie założenie, że dla pewnego k dowodzony wzór jest prawdziwy. Jak to rozumieć? Zakładam, że dowodzony wzór jest prawdziwy. I później korzystam z niego do udowodnienia, że jest też prawdziwy dla k+1. Tak po prostu sobie zakładam? O co tu chodzi?

[Janusz Tracz]

W drugim kroku sprawdzasz prawdziwość implikacji jako całości, patrzysz czy prawdziwe jest zdanie

\(\displaystyle{ \left( \forall n\in\mathbb{N}\right) \left( \phi(n)\Rightarrow\phi(n+1)\right) }\)

jako całość. To zdanie ma formę twierdzenie, że dla każdego \(\displaystyle{ n}\) coś tam... zatem ustalasz sobie dowolne \(\displaystyle{ n}\) takie, że \(\displaystyle{ \phi(n)}\) i sprawdzasz czy z tego jesteś w stanie coś powiedzieć o \(\displaystyle{ \phi(n+1)}\).

Jak udowodnisz pierwszy i drugi krok to wiesz, że \(\displaystyle{ \phi(1)}\) jest prawdą jak również (skoro zachodzi dla każdego to dla szczególnych też)

\(\displaystyle{ \phi(1) \Rightarrow \phi(2)}\)

\(\displaystyle{ \phi(2) \Rightarrow \phi(3)}\)

itd. Zatem zdanie \(\displaystyle{ \left( \forall n\in\mathbb{N}\right) \phi(n) }\) jest udowodnione.

Może i nie jest to ultra ścisłe wyjaśnienie ale uważam, że oddaje to sedno indukcji (przynajmniej tej w podstawowej wersji).

[a4karo]

W drugim kroku nie zakładasz prawdziwości zdania \(\phi(n)\). Pokazujesz tylko, że jeżeli "jakimś cudem" \(\phi(n)\) jest prawdziwe, to prawdziwe jest również \(\phi(n+1)\). Jeżeli to Ci się uda, to zasada indukcji mówi, że \(\phi\) jest prawdziwe dla wszystkich \(n\)

[psi]

A co by było gdybym założył w drugim kroku, że wzór który dowodzę jest fałszywy?

[Jan Kraszewski]

A co by było gdybym założył w drugim kroku, że wzór który dowodzę jest fałszywy?

Zrobiłbyś coś, co nie ma sensu.

Warto pamiętać, że to, co nazywasz "dowodem indukcyjnym" jest tak naprawdę sprawdzeniem założeń Zasady Indukcji Matematycznej.

Możesz zerknąć tu.

JK