Indukcja matematyczna
Z Skrypty dla studentów Ekonofizyki UPGOW
(Różnice między wersjami)
(→Przykłady wykorzystania indukcji matematycznej) |
|||
| (Nie pokazano 2 wersji pomiędzy niniejszymi.) | |||
| Linia 1: | Linia 1: | ||
[[Category:KURS MATEMATYKI]] | [[Category:KURS MATEMATYKI]] | ||
| - | + | Indukcję matematyczną wykorzystujemy do dowodzenia twierdzeń i wzorów (równości, nierówności) dotyczących liczb naturalnych. | |
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
== Praktyczne stosowanie indukcji matematycznej == | == Praktyczne stosowanie indukcji matematycznej == | ||
| - | W praktyce | + | W praktyce indukcję matematyczną stosujemy w następujących trzech krokach: |
#Udowadniamy prawdziwość twierdzenia dla pewnej liczby naturalnej <math>n</math>, przy czym najczęściej <math>n=1</math>. Do udowodnienia twierdzenia dla <math>n</math> zazwyczaj wystarcza wstawienie <math>n</math> do wzoru, który mamy dowieść i sprawdzenie, czy lewa strona wzoru jest równa prawej. | #Udowadniamy prawdziwość twierdzenia dla pewnej liczby naturalnej <math>n</math>, przy czym najczęściej <math>n=1</math>. Do udowodnienia twierdzenia dla <math>n</math> zazwyczaj wystarcza wstawienie <math>n</math> do wzoru, który mamy dowieść i sprawdzenie, czy lewa strona wzoru jest równa prawej. | ||
| - | #Zakładamy, ze twierdzenie jest prawdziwe dla pewnej liczby naturalnej <math>m | + | #Zakładamy, ze twierdzenie jest prawdziwe dla pewnej liczby naturalnej <math>m \geq n</math>. Jest to założenie indukcyjne. |
| - | #Udowadniamy prawdziwość twierdzenia dla <math>m+1</math>, korzystając z założenia indukcyjnego, czyli z prawdziwości twierdzenia dla <math>m</math>. Jest to teza indukcyjna | + | #Udowadniamy prawdziwość twierdzenia dla <math>m+1</math>, korzystając z założenia indukcyjnego, czyli z prawdziwości twierdzenia dla <math>m</math>. Jest to teza indukcyjna. |
| - | Udowodnienie tezy indukcyjnej jest równoważne z prawdziwością | + | 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 <math>n=1</math>. |
| - | + | Symboliczny zapis zasady indukcji matematycznej wygląda następująco: jeżeli <math>T(m)</math> jest funkcją zdaniową argumentu <math>m \in N</math>, to: | |
| - | + | ||
| - | + | ||
| - | + | ||
| - | * | + | <math>\biggl\{ T(1) \land \bigwedge_{m \in N} \Bigr[T(m)\Rightarrow T(m+1)\Bigr] \biggl\} \Rightarrow \bigwedge_{m \in N} T(m)</math> |
| + | |||
| + | == Przykłady wykorzystania indukcji matematycznej == | ||
| + | *Korzystając z zasady indukcji matematycznej wykaż, że dla każdej liczby naturalnej <math>n \geq 1 </math> prawdziwe jest równanie | ||
| + | :<math>1+2+3+\ldots+n=\frac{n(n+1)}{2}</math> | ||
# Sprawdzamy równanie dla <math>n=1</math> | # Sprawdzamy równanie dla <math>n=1</math> | ||
| Linia 46: | Linia 32: | ||
Udowodniliśmy, że jeżeli równanie jest prawdziwe dla liczby <math>k</math>, to jest ono prawdziwe dla liczby <math>k+1</math>. Oznacza to, że jeżeli jest prawdziwie dla liczby <math>1</math> to jest ono prawdziwe dla wszystkich liczb naturalnych. | Udowodniliśmy, że jeżeli równanie jest prawdziwe dla liczby <math>k</math>, to jest ono prawdziwe dla liczby <math>k+1</math>. Oznacza to, że jeżeli jest prawdziwie dla liczby <math>1</math> to jest ono prawdziwe dla wszystkich liczb naturalnych. | ||
| + | |||
| + | *Wykazać, że liczba postaci <math>5^n - 1, n \in \mathbb{N}</math> jest podzielna (czyli dzieli się bez reszty) przez 4. | ||
| + | |||
| + | # Sprawdzamy podzielność dla <math>n=1</math>. Otrzymujemy <math>5^1 - 1 = 4</math>. Oczywiście 4 jest podzielne przez 4. | ||
| + | # Zakładamy, że liczba postaci <math>5^k - 1</math> jest podzielna przez cztery, czyli może być zapisana jako | ||
| + | #: :<math>5^k - 1 = 4m, m \in \mathbb{N}</math> | ||
| + | # Sprawdzamy prawdziwość dla <math>k+1</math>, czyli chcemy wykazać, że liczba postaci <math>5^{k+1} - 1 = 4p, p \in \mathbb{N}</math>. Zatem trzeba wykazać, że <math>p</math> jest liczbą naturalną. | ||
| + | #: :<math>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</math> | ||
| + | gdzie z postaci liczby <math>p = 5^k + m</math> widzimy od razu, że jest to liczba naturalna, ponieważ <math>m \in \mathbb{N}</math> 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: <math>(1+a)^n \geq 1 + na, \quad a \gt -1, \quad n \geq 0</math>. | ||
| + | |||
| + | # Dla <math>n = 0</math> otrzymujemy <math>(1 + a)^0 =1 \geq 1 + 0a</math> | ||
| + | # Zakładamy prawdziwość (założenie indukcyjne) nierówności Bernoulliego dla <math>k</math>: <math>(1+a)^k \geq 1 + ka</math> | ||
| + | # Sprawdzamy nierówność Bernoulliego dla <math>k+1</math> | ||
| + | #: :<math>(1+a)^{k+1} \geq 1 + (k+1)a</math> | ||
| + | #: :<math>(1+a)^k (1+a) \geq (1+ka)(1+a)</math> gdzie wykorzystaliśmy założenie indukcyjne i pamiętamy, że <math>a \gt -1</math>, czyli <math>1+a \gt 0.</math> Po przekształceniu prawej strony nierówności dostajemy | ||
| + | #: :<math>(1+a)^{k+1} \geq 1 + a(k+1) + a^2k \geq 1 + (k+1)a,</math> | ||
| + | ponieważ <math>a^2k \geq 0</math>. Tym samym wykazaliśmy prawdziwość nierówności Bernoulliego dla każdego <math>n \in \mathbb{N}</math>. | ||
== Zadania == | == Zadania == | ||
| Linia 54: | Linia 60: | ||
#Korzystając z zasady indukcji matematycznej wykaż, że dla dowolnego <math> n\in\mathbb{N}</math> i <math>n \geq 2</math>, zachodzi nierówność: | #Korzystając z zasady indukcji matematycznej wykaż, że dla dowolnego <math> n\in\mathbb{N}</math> i <math>n \geq 2</math>, zachodzi nierówność: | ||
#: :<math>\frac{\sqrt{2}}{1}+\frac{\sqrt{3}}{2}+\ldots\frac{\sqrt{n}}{n-1}>\sqrt{n-1}\; .\,</math> | #: :<math>\frac{\sqrt{2}}{1}+\frac{\sqrt{3}}{2}+\ldots\frac{\sqrt{n}}{n-1}>\sqrt{n-1}\; .\,</math> | ||
| - | #Wykazać, że dla dowolnego <math>n\in\mathbb{N}\,</math> i <math>n\geq 2\,</math> liczba postaci <math>4^n+6n-10\,</math> jest podzielna przez | + | #Wykazać, że dla dowolnego <math>n\in\mathbb{N}\,</math> i <math>n\geq 2\,</math> liczba postaci <math>4^n+6n-10\,</math> jest podzielna przez <math>9</math>. |
Aktualna wersja na dzień 09:31, 31 mar 2015
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:
- 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.
- Zakładamy, ze twierdzenie jest prawdziwe dla pewnej liczby naturalnej \(m \geq n\). Jest to założenie indukcyjne.
- 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}\]
- Sprawdzamy równanie dla \(n=1\)
- \[L=1\]
- \[P=\frac{\color{green}{1}(\color{green}{1}+1)}{2}=1\]
- 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}\]
- 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.
- Sprawdzamy podzielność dla \(n=1\). Otrzymujemy \(5^1 - 1 = 4\). Oczywiście 4 jest podzielne przez 4.
- 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}\]
- 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\).
- Dla \(n = 0\) otrzymujemy \((1 + a)^0 =1 \geq 1 + 0a\)
- Zakładamy prawdziwość (założenie indukcyjne) nierówności Bernoulliego dla \(k\): \((1+a)^k \geq 1 + ka\)
- 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
- 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\).