Z Skrypty dla studentów Ekonofizyki UPGOW

Spis treści [ukryj] 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\,.