Z Skrypty dla studentów Ekonofizyki UPGOW
(Utworzył nową stronę „== Zasada indukcji matematycznej == Zasada indukcji matematycznej jest metodą dowodzenia twierdzeń o liczbach naturalnych. Przypuśćmy, że <math>T(n)</math> jest pe...”) |
(→Indukcją zupełna) |
||
| Linia 9: | Linia 9: | ||
Niech <math>T(n)</math> jest pewnym wyrażeniem, w którym jedyną zmienną jest n i dziedzina tej zmiennej zawiera wszystkie liczby naturalne. Załóżmy, że | Niech <math>T(n)</math> jest pewnym wyrażeniem, w którym jedyną zmienną jest n i dziedzina tej zmiennej zawiera wszystkie liczby naturalne. Załóżmy, że | ||
#dla każdej liczby naturalnej <math>n\in \mathbb N </math> zachodzi: | #dla każdej liczby naturalnej <math>n\in \mathbb N </math> zachodzi: | ||
| - | <math> (\forall m<n)(T(m))\quad \implies \quad T(n)</math>. | + | :<math> (\forall m<n)(T(m))\quad \implies \quad T(n)</math>. |
Wówczas <math>T(n)</math> jest prawdziwe dla każdego <math>n\in \mathbb N</math>. | Wówczas <math>T(n)</math> jest prawdziwe dla każdego <math>n\in \mathbb N</math>. | ||
| + | |||
== Praktyczne stosowanie indukcji == | == Praktyczne stosowanie indukcji == | ||
Dowód twierdzenia przeprowadzamy w trzech krokach: | Dowód twierdzenia przeprowadzamy w trzech krokach: | ||
Wersja z 19:47, 12 gru 2013
Spis treści |
Zasada indukcji matematycznej
Zasada indukcji matematycznej jest metodą dowodzenia twierdzeń o liczbach naturalnych. Przypuśćmy, że \(T(n)\) jest pewnym wyrażeniem w którym jedyną zmienną jest \(n\) i dziedzina tej zmiennej zawiera wszystkie liczby naturalne. Załóżmy, że
- \(T(1)\) jest zdaniem prawdziwym
- \(\forall n\in \mathbb N \) zachodzi
\[T(n)\quad \implies \quad T(n+1)\]. Wówczas \(T(n)\) jest prawdziwe dla każdej liczby naturalnej \(n\in \mathbb N\).
Indukcją zupełna
Niech \(T(n)\) jest pewnym wyrażeniem, w którym jedyną zmienną jest n i dziedzina tej zmiennej zawiera wszystkie liczby naturalne. Załóżmy, że
- dla każdej liczby naturalnej \(n\in \mathbb N \) zachodzi:
\[ (\forall m<n)(T(m))\quad \implies \quad T(n)\]. Wówczas \(T(n)\) jest prawdziwe dla każdego \(n\in \mathbb N\).
Praktyczne stosowanie indukcji
Dowód twierdzenia przeprowadzamy w trzech krokach:
- Udowadniamy prawdziwość twierdzenia dla pewnej liczby naturalnej \(n_0\) (często \(n_0=1\),
- Zakładamy, ze twierdzenie jest prawdziwe dla pewnej liczby naturalnej \(m \ge n_0\)
- Udowadniamy prawdziwość tego twierdzenia dla \(m+1\), korzystając z prawdziwości dla \(m\). Czyli wykazujemy, że prawdziwa jest implikacja \( T(m) \implies T(m+1)\)
Pierwszy krok to sprawdzenie, natomiast drugi to tzw. krok indukcyjny, w którym powołując się na założenie indukcyjne ( \(T(m)\) jest prawdziwe, \(m \ge n_{0}\)) wyprowadzamy prawdziwość tezy indukcyjnej \(T(m+1)\)
Zadania
- Korzystając z zasady indukcji matematycznej wykaż, że dla dowolnego \( n\in\mathbb{N}\) prawdziwa jest równość:
- \[1^3+3^3+\ldots +(2n+1)^3=2(n+1)^4-(n+1)^2\; .\,\]
- Korzystając z zasady indukcji matematycznej wykaż, że dla dowolnego \( n\in\mathbb{N}\) i \(n \geq 2\), prawdziwa jest równość:
- \[\frac{1}{2^2-1}+\frac{1}{3^2-1}+\ldots\frac{1}{n^2-1}=\frac{(3n+2)(n-1)}{4n(n+1)}\; .\,\]
- Korzystając z zasady indukcji matematycznej wykaż, że dla dowolnego \( n\in\mathbb{N}\) i \(n \geq 2\), zachodzi nierówność:
- \[\frac{\sqrt{2}}{1}+\frac{\sqrt{3}}{2}+\ldots\frac{\sqrt{n}}{n-1}>\sqrt{n-1}\; .\,\]
- Wykazać, że dla dowolnego \(n\in\mathbb{N}\,\) i \(n\geq 2\,\) liczba postaci \(4^n+6n-10\,\) jest podzielna przez 9\,.