Z Skrypty dla studentów Ekonofizyki UPGOW

Wersja z 14:28, 19 gru 2013 (pokaż źródło) SewerynKowalski (dyskusja | edycje) ← poprzednia edycja		Aktualna wersja na dzień 09:31, 31 mar 2015 (pokaż źródło) SewerynKowalski (dyskusja | edycje) (→Przykłady wykorzystania indukcji matematycznej)
(Nie pokazano 3 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 metodą dowodzenia twierdzeń o liczbach naturalnych.	+	== Praktyczne stosowanie indukcji matematycznej ==
-	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	+	W praktyce indukcję matematyczną stosujemy w następujących trzech krokach:
-	#<math>T(1)</math> jest zdaniem prawdziwym	+	#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.
-	#<math>\forall n\in \mathbb N </math> zachodzi	+	#Zakładamy, ze twierdzenie jest prawdziwe dla pewnej liczby naturalnej <math>m \geq n</math>. Jest to założenie indukcyjne.
-	:<math>T(n)\quad \implies \quad T(n+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.
-	Wówczas <math>T(n)</math> jest prawdziwe dla każdej liczby naturalnej <math>n\in \mathbb 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 ==	+	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>.
-	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>,	+	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:
-	#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>	+	<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>
		+	#: :<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.
		+
		+	*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>.
-	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 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\).