Z Skrypty dla studentów Ekonofizyki UPGOW
Linia 1: | Linia 1: | ||
[[Category:KURS MATEMATYKI]] | [[Category:KURS MATEMATYKI]] | ||
== Zasada indukcji matematycznej == | == Zasada indukcji matematycznej == | ||
- | Zasada indukcji matematycznej jest | + | 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> | |
- | #<math> | + | #jeżeli zdanie <math>Z(n)</math> jest prawdziwe |
- | #<math>\ | + | #oraz jeżeli dla dowolnej liczby naturalnej <math>m \geq n</math>, prawdziwa jest implikacja (czyli wynikanie) |
- | :<math> | + | :<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 == | == 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> | ||
- | + | 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. | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | |||
== 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
- 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\)
- jeżeli zdanie \(Z(n)\) jest prawdziwe
- 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:
- 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 = 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. 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
- 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.
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.