indukcja pytanie :): Cześć, Mam takie pytanie dt. indukcji. Dowodzenie indukcyjne opiera się na implikacji P(n) => P(n+1) i pokazaniu jej zachodzenia dla pierwszego elementu. I żeby zdanie drugie ( P(n+1) ) było tezą prawdziwą, prawdziwa musi być cała indukcja i prawdziwe zdanie pierwsze. Przeprowadzając dowód indukcyjny, poczynamy założenie, że prawdziwe jest P(n). W takim razie wedle tego jest to dziwne, że zakładamy coś, co musi być prawdą. Mam nadzieję, że widać, gdzie źle rozumuję i liczę na Waszą pomoc pozdro

Trivial: Idea indukcji jest prosta. Chcemy wykazać, że w liczbach naturalnych zachodzi twierdzenie T dla liczby n. Oznaczmy to jako T(n). Możemy brać każdą liczbę naturalną i pokazać, że zachodzi: T(0), T(1), T(2), T(3), ... Ale w ten sposób nigdy nie udowodnimy, że T(n) zachodzi dla każdego naturalnego n. Natomiast jeśli pokażemy, że dla każdego n mamy zależność: T(n) ⇒ T(n+1) to wystarczy udowodnić T(0). Dlaczego? Ano dlatego, że T(0) ⇒ T(1) ⇒ T(2) ⇒ T(3) ⇒ ... i tym samym musi zachodzi dla każdego n.

Trivial: Na przykładzie: Chcemy udowodnić, że dla każdego n naturalnego zachodzi: T(n) = (n² ≥ n) // predykat Możemy brać każde n naturalne po kolei i sprawdzać: T(0) = (0 ≥ 0) = Prawda T(1) = (1 ≥ 1) = Prawda T(2) = (4 ≥ 1) = Prawda T(3) = (9 ≥ 1) = Prawda Ale nigdy tego nie udowodnimy dla każdego n, gdyż liczb naturalnych jest nieskończenie wiele. Natomiast jeśli pokażemy, że: T(n) ⇒ T(n+1) Czyli (n² ≥ n) ⇒ [(n+1)² ≥ (n+1)] To wystarczy pokazać, że T(0) jest prawdą. Zatem zakładamy n² ≥ n i sprawdzamy czy da się z tego wywnioskować (n+1)² ≥ (n+1) (n+1)² = n²+2n+1 ≥^2n≥0 n²+1 ≥^zał.ind. n+1 Zatem (n+1)² ≥ n+1 przy założeniu, że n² ≥ n. Wystarczy zatem pokazać, że 0² ≥ 0, co jest prawdą.

S: " jeśli pokażemy, że dla każdego n mamy zależność: T(n) ⇒ T(n+1) to wystarczy udowodnić T(0). Dlaczego? Ano dlatego, że T(0) ⇒ T(1) ⇒ T(2) ⇒ T(3) ⇒ ... i tym samym musi zachodzi dla każdego n. " Dobrze, ale ciągle nie rozumiem, dlaczego dowód tej implikacji opieramy na założeniu o prawdziwości T(n) skoro co do niego nie mamy pewności.

asdf: właśnie dlatego się dowodzi na przykładzie, np. T(0), a następnie się to udowadnia, dla T(n+1). podkreślam: udowadnia, a nie wyprowadza.

S: nic mi to nie wyjaśnia, pokazałeś dla 0 − ok. Ale nie dla n

Trivial: Indukcja działa tak: 1) Przypadek bazowy jest prawdziwy T(0) = prawda. 2) T(0) ⇒ T(1) // zakładając T(0) dowodzimy T(1) T(1) ⇒ T(2) // zakładając T(1) dowodzimy T(2) T(2) ⇒ T(3) // zakładając T(2) dowodzimy T(3) T(3) ⇒ T(4) // zakładając T(3) dowodzimy T(4) T(4) ⇒ T(5) // zakładając T(4) dowodzimy T(5) ... Zauważ, że jest to równoważne z pokazaniem T(n) ⇒ T(n+1) w ogólnym przypadku.

S: To rozumiem, czyli zakładamy że działa dla n. Ale dlaczego możemy założyć, że jeśli n to n+1?

Trivial: Nie możemy tego założyć. To trzeba wykazać. "Zakładając że T(n) należy wykazać T(n+1)".

asdf: To jak to rozumiesz, to dalej: nie zawsze udowadnia się dla n = 0 na początku np. udowodnij, że: n² −2 > n dla każdego n > 2 1^o. Udowadnia się, że dla n = 3: n² − 2 > n ⇒ 3² − 2 > 3 ⇒ 7 > 3 (prawda) 2^o. Teraz trzeba udowodnić, że zachodzi to dla n = n+1, tzn: (n+1)² − 2 > n+1} n² + 2n + 1 − 2 > n+1 n² + 2n − 1 > n+1 n² +2n > n+2 n² − 2 + 2n > n z pierwszego założenia: n² − 2 > n (prawda) n jest dodatnie, czyli n² − 2n + 2n > n, bo: n² − 2 + 2n > n² − 2 > n ⇒ n² − 2 + 2n > n

asdf: możesz to porównać z takim działaniem: 2 > 1, to na pewno 3 > 1, tu jest to samo: n² − 2 > n, więc na pewno n² − 2 + 2n > n