Indukcja matematyczna

Z Skrypty dla studentów Ekonofizyki UPGOW

(Różnice między wersjami)
Linia 1: Linia 1:
[[Category:KURS MATEMATYKI]]
[[Category:KURS MATEMATYKI]]
== Zasada indukcji matematycznej ==
== Zasada indukcji matematycznej ==
-
Zasada indukcji matematycznej jest metodą dowodzenia twierdzeń o liczbach 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
-
Przypuśćmy, że <math>T(n)</math> jest pewnym wyrażeniem w którym jedyną zmienną jest <math>n</math> i dziedzina tej zmiennej zawiera wszystkie liczby naturalne. Załóżmy, że
+
#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>
-
#<math>T(1)</math> jest zdaniem prawdziwym
+
#jeżeli zdanie <math>Z(n)</math> jest prawdziwe
-
#<math>\forall n\in \mathbb N </math> zachodzi
+
#oraz jeżeli dla dowolnej liczby naturalnej <math>m \geq n</math>, prawdziwa jest implikacja (czyli wynikanie) 
-
:<math>T(n)\quad \implies \quad T(n+1)</math>.
+
:<math>Z(m)\quad \implies \quad Z(m+1).</math>
-
Wówczas <math>T(n)</math> jest prawdziwe dla każdej liczby naturalnej <math>n\in \mathbb N</math>.
+
to wtedy zdanie <math>Z(m)</math> jest prawdziwe dla każdej liczby naturalnej <math>m \geq n</math>.
 +
 
 +
<!--
== Indukcją zupełna ==
== 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
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
Linia 12: Linia 14:
:<math> (\forall m<n)(T(m))\quad \implies \quad T(n)</math>
:<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>.
Wówczas <math>T(n)</math> jest prawdziwe dla każdego <math>n\in \mathbb N</math>.
 +
-->
 +
 +
== Praktyczne stosowanie indukcji matematycznej ==
 +
W praktyce idukcję matematyczną stosujemy w nastepują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. 
 +
#Zakładamy, ze twierdzenie jest prawdziwe dla pewnej liczby naturalnej <math>m = 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>.
 +
 +
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>.
 +
 +
== Przykład wykorzystania indukcji matematycznej ==
 +
*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
 +
 +
# Sprawdzamy równanie dla <math>n=1</math>
 +
#: :<math>L=1</math>
 +
#: :<math>P=\frac{\color{green}{1}(\color{green}{1}+1)}{2}=1</math>
 +
# Zakładamy, że prawdziwe jest rówanie dla pewnej liczby <math>\color{green}{k} \geq 1 </math>
 +
#: :<math>1+2+3+\ldots+\color{green}{k}=\frac{\color{green}{k}(\color{green}{k}+1)}{2}</math>
 +
# Dowodzimy prawdziwości równania dla <math>k+1</math>
 +
#: :<math>1+2+3+\ldots+k+\color{green}{k+1}=\frac{(\color{green}{k+1})(\color{green}{k+1}+1)}{2}</math>
 +
 +
:<math>L=1+2+3+\ldots+k+\color{green}{k+1}=</math>
 +
:korzystamy z punktu 2
 +
:<math>=\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}=</math>
 +
:<math>=\frac{(k+1)(k+2)}{2}=P</math>
 +
:<math>L=P</math>
-
== Praktyczne stosowanie indukcji ==
+
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.
-
Dowód twierdzenia przeprowadzamy w trzech krokach:
+
-
#Udowadniamy prawdziwość twierdzenia dla pewnej liczby naturalnej <math>n_0</math> (często <math>n_0=1</math>,
+
-
#Zakładamy, ze twierdzenie jest prawdziwe dla pewnej liczby naturalnej <math>m \ge n_0</math>
+
-
#Udowadniamy prawdziwość tego twierdzenia dla <math>m+1</math>, korzystając z prawdziwości dla <math>m</math>. Czyli wykazujemy, że prawdziwa jest implikacja <math> T(m) \implies T(m+1)</math>
+
-
Pierwszy krok to sprawdzenie, natomiast drugi to tzw. krok indukcyjny, w którym powołując się na założenie indukcyjne ( <math>T(m)</math> jest prawdziwe, <math>m  \ge n_{0}</math>) wyprowadzamy prawdziwość tezy indukcyjnej <math>T(m+1)</math>
 
== Zadania ==
== Zadania ==
#Korzystając z zasady indukcji matematycznej wykaż, że dla dowolnego <math> n\in\mathbb{N}</math> prawdziwa jest równość:
#Korzystając z zasady indukcji matematycznej wykaż, że dla dowolnego <math> n\in\mathbb{N}</math> prawdziwa jest równość:
Linia 27: Linia 54:
#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 '''''9'''''.

Wersja z 20:00, 6 mar 2014

Spis treści

Zasada indukcji matematycznej

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

  1. jeżeli dla pewnej ustalonej liczby naturalnej \(n\) dane jest zdanie \(Z(m)\) (może to być również wzór lub twierdzenie) dla każdej liczby naturalnej \(m \geq n\)
  2. jeżeli zdanie \(Z(n)\) jest prawdziwe
  3. oraz jeżeli dla dowolnej liczby naturalnej \(m \geq n\), prawdziwa jest implikacja (czyli wynikanie)

\[Z(m)\quad \implies \quad Z(m+1).\] to wtedy zdanie \(Z(m)\) jest prawdziwe dla każdej liczby naturalnej \(m \geq n\).


Praktyczne stosowanie indukcji matematycznej

W praktyce idukcję matematyczną stosujemy w nastepują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 = 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. Tym samym wykazujemy, że prawdziwa jest implikacja \( Z(m) \implies Z(m+1)\).

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 \(n=1\).

Przykład wykorzystania indukcji matematycznej

  • Zadanie

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}\]

  • Rozwiązanie
  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.

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.