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]]
-
== Zasada indukcji matematycznej ==
+
Indukcję matematyczną wykorzystujemy do dowodzenia twierdzeń i wzorów (równości, nierówności) dotyczących liczb naturalnych.
-
Zasada indukcji matematycznej jest stosowana do dowodzenia twierdzeń i wykazywania prawdziwości wzorów dotyczących liczb naturalnych. Można ją przedstawić w następujący sposób
+
-
#jeżeli dla pewnej ustalonej liczby naturalnej <math>n</math> dane jest zdanie <math>Z(m)</math> (może to być również wzór lub twierdzenie) dla każdej liczby naturalnej <math>m \geq n</math>
+
-
#jeżeli zdanie <math>Z(n)</math> jest prawdziwe
+
-
#oraz jeżeli dla dowolnej liczby naturalnej <math>m \geq n</math>, prawdziwa jest implikacja (czyli wynikanie) 
+
-
:<math>Z(m)\quad \implies \quad Z(m+1).</math>
+
-
to wtedy zdanie <math>Z(m)</math> jest prawdziwe dla każdej liczby naturalnej <math>m \geq n</math>.
+
-
 
+
-
<!--
+
-
== Indukcją zupełna ==
+
-
Niech <math>T(n)</math> jest pewnym wyrażeniem, w którym jedyną zmienną jest n i dziedzina tej zmiennej zawiera wszystkie liczby naturalne. Załóżmy, że
+
-
#dla każdej liczby naturalnej <math>n\in \mathbb N </math> zachodzi:
+
-
:<math> (\forall m<n)(T(m))\quad \implies \quad T(n)</math>
+
-
Wówczas <math>T(n)</math> jest prawdziwe dla każdego <math>n\in \mathbb N</math>.
+
-
-->
+
-
 
+
== Praktyczne stosowanie indukcji matematycznej ==
== Praktyczne stosowanie indukcji matematycznej ==
-
W praktyce idukcję matematyczną stosujemy w nastepujących trzech krokach:
+
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 = n</math>. Jest to założenie indukcyjne.  
+
#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. Tym samym wykazujemy, że prawdziwa jest implikacja <math> Z(m) \implies Z(m+1)</math>.  
+
#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ą zdania (twierdzenia, wzoru) dla wszystkich liczb naturalnych, jeżeli udowodniliśmy prawdziwość zdania (twierdzenia, wzoru) dla <math>n=1</math>.
+
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>.
-
== Przykład wykorzystania indukcji matematycznej ==
+
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:
-
*Zadanie
+
-
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>
+
-
*Rozwiązanie
+
<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 '''''9'''''.
+
#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:

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