Z Skrypty dla studentów Ekonofizyki UPGOW

Indukcję matematyczną wykorzystujemy do dowodzenia twierdzeń i wzorów (równości, nierówności) dotyczących liczb naturalnych.

Praktyczne stosowanie indukcji matematycznej

W praktyce indukcję matematyczną stosujemy w następujących trzech krokach:

1. Udowadniamy prawdziwość twierdzenia dla pewnej liczby naturalnej $n$, przy czym najczęściej $n=1$. Do udowodnienia twierdzenia dla $n$ zazwyczaj wystarcza wstawienie $n$ do wzoru, który mamy dowieść i sprawdzenie, czy lewa strona wzoru jest równa prawej.
2. Zakładamy, ze twierdzenie jest prawdziwe dla pewnej liczby naturalnej $m \geq n$. Jest to założenie indukcyjne.
3. Udowadniamy prawdziwość twierdzenia dla $m+1$, korzystając z założenia indukcyjnego, czyli z prawdziwości twierdzenia dla $m$. Jest to teza indukcyjna.

Udowodnienie tezy indukcyjnej jest równoważne z prawdziwością twierdzenia (wzoru) dla wszystkich liczb naturalnych, jeżeli udowodniliśmy prawdziwość zdania (twierdzenia, wzoru) dla $n=1$.

Symboliczny zapis zasady indukcji matematycznej wygląda następująco: jeżeli $T(m)$ jest funkcją zdaniową argumentu $m \in N$, to:

$\biggl\{ T(1) \land \bigwedge_{m \in N} \Bigr[T(m)\Rightarrow T(m+1)\Bigr] \biggl\} \Rightarrow \bigwedge_{m \in N} T(m)$

Przykłady wykorzystania indukcji matematycznej

• Korzystając z zasady indukcji matematycznej wykaż, że dla każdej liczby naturalnej $n \geq 1$ prawdziwe jest równanie

$$1+2+3+\ldots+n=\frac{n(n+1)}{2}$$

1. Sprawdzamy równanie dla $n=1$

   $$L=1$$

   $$P=\frac{\color{green}{1}(\color{green}{1}+1)}{2}=1$$

2. Zakładamy, że prawdziwe jest rówanie dla pewnej liczby $\color{green}{k} \geq 1$

   $$1+2+3+\ldots+\color{green}{k}=\frac{\color{green}{k}(\color{green}{k}+1)}{2}$$

3. Dowodzimy prawdziwości równania dla $k+1$

   $$1+2+3+\ldots+k+\color{green}{k+1}=\frac{(\color{green}{k+1})(\color{green}{k+1}+1)}{2}$$

$$L=1+2+3+\ldots+k+\color{green}{k+1}=$$

korzystamy z punktu 2

$$=\frac{k(k+1)}{2}+(k+1)=\frac{k(k+1)}{2}+\frac{2(k+1)}{2}=\frac{k(k+1)+2(k+1)}{2}=$$ $$=\frac{(k+1)(k+2)}{2}=P$$ $$L=P$$

Udowodniliśmy, że jeżeli równanie jest prawdziwe dla liczby $k$, to jest ono prawdziwe dla liczby $k+1$. Oznacza to, że jeżeli jest prawdziwie dla liczby $1$ to jest ono prawdziwe dla wszystkich liczb naturalnych.

• Wykazać, że liczba postaci $5^n - 1, n \in \mathbb{N}$ jest podzielna (czyli dzieli się bez reszty) przez 4.

1. Sprawdzamy podzielność dla $n=1$. Otrzymujemy $5^1 - 1 = 4$. Oczywiście 4 jest podzielne przez 4.
2. Zakładamy, że liczba postaci $5^k - 1$ jest podzielna przez cztery, czyli może być zapisana jako

   $$5^k - 1 = 4m, m \in \mathbb{N}$$

3. Sprawdzamy prawdziwość dla $k+1$, czyli chcemy wykazać, że liczba postaci $5^{k+1} - 1 = 4p, p \in \mathbb{N}$. Zatem trzeba wykazać, że $p$ jest liczbą naturalną.

   $$5^{k+1} - 1 = 5^k 5 - 1 = 5^k (4 + 1) - 1 = 5^k 4 + 5^k - 1 = 5^k 4 + 4m = 4 (5^k + m) = 4p$$

gdzie z postaci liczby $p = 5^k + m$ widzimy od razu, że jest to liczba naturalna, ponieważ $m \in \mathbb{N}$ z założenia indukcyjnego.

• Indukcję matematyczną można także stosować do wykazywania prawdziwości nierówności, co pokażemy na przykładzie nierówności Bernoulliego: $(1+a)^n \geq 1 + na, \quad a \gt -1, \quad n \geq 0$.

1. Dla $n = 0$ otrzymujemy $(1 + a)^0 =1 \geq 1 + 0a$
2. Zakładamy prawdziwość (założenie indukcyjne) nierówności Bernoulliego dla $k$: $(1+a)^k \geq 1 + ka$
3. Sprawdzamy nierówność Bernoulliego dla $k+1$

   $$(1+a)^{k+1} \geq 1 + (k+1)a$$

   $$(1+a)^k (1+a) \geq (1+ka)(1+a)$$ gdzie wykorzystaliśmy założenie indukcyjne i pamiętamy, że $a \gt -1$, czyli $1+a \gt 0.$ Po przekształceniu prawej strony nierówności dostajemy

   $$(1+a)^{k+1} \geq 1 + a(k+1) + a^2k \geq 1 + (k+1)a,$$

ponieważ $a^2k \geq 0$. Tym samym wykazaliśmy prawdziwość nierówności Bernoulliego dla każdego $n \in \mathbb{N}$.

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$.