Tekst źródłowy

[[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 ==
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.  
#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. 

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>
#: :<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>.

== Zadania ==
#Korzystając z zasady indukcji matematycznej wykaż, że dla dowolnego <math> n\in\mathbb{N}</math> prawdziwa jest równość:
#: :<math>1^3+3^3+\ldots +(2n+1)^3=2(n+1)^4-(n+1)^2\; .\,</math>
#Korzystając z zasady indukcji matematycznej wykaż, że dla dowolnego <math> n\in\mathbb{N}</math> i <math>n \geq   2</math>, prawdziwa jest równość:
#: :<math>\frac{1}{2^2-1}+\frac{1}{3^2-1}+\ldots\frac{1}{n^2-1}=\frac{(3n+2)(n-1)}{4n(n+1)}\; .\,</math>
#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>
#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>.