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\).