Z Skrypty dla studentów Ekonofizyki UPGOW

Spis treści 1 Zasada indukcji matematycznej 2 Indukcją zupełna 3 Praktyczne stosowanie indukcji 4 Zadania

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

1. \(T(1)\) jest zdaniem prawdziwym
2. \(\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

1. 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:

1. Udowadniamy prawdziwość twierdzenia dla pewnej liczby naturalnej \(n_0\) (często \(n_0=1\),
2. Zakładamy, ze twierdzenie jest prawdziwe dla pewnej liczby naturalnej \(m \ge n_0\)
3. 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

1. 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\; .\,\]

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)}\; .\,\]

3. 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}\; .\,\]

4. Wykazać, że dla dowolnego \(n\in\mathbb{N}\,\) i \(n\geq 2\,\) liczba postaci \(4^n+6n-10\,\) jest podzielna przez 9\,.