Do czego służy indukcja matematyczna?Schemat indukcji matematycznej Baza indukcyjna Krok indukcyjny Wnioski Przykłady Zadania

Do czego służy indukcja matematyczna?

Indukcja matematyczna to bardzo uniwersalne narzędzie do dowodzenia różnych rzeczy.

Schemat indukcji matematycznej

Indukcja matematyczna składa się z bazy indukcyjnej i kroku indukcyjnego.

Baza indukcyjna

Baza indukcyjna to przykład (możliwie jak najmniejszy), dla którego dana teza jest spełniona np. dla $ n = 1 $: $$ \sum^{n}_{i = 1}{i} = 1 = \frac{n(n+1)}{2} = \frac{1 \cdot 2}{2} = 1 $$

Krok indukcyjny

Krok indukcyjny mówi, że jeśli teza jest spełniona dla $n$ - założenie indukcyjne to dla $n+1$ też jest spełniona - teza indukcyjna.

Np. jeśli $ \sum^{n}_{i = 1}{i} = \frac{n(n+1)}{2} $ to $ \sum^{n+1}_{i = 1}{i} = \sum^{n}_{i = 1}{i} + n+1 = \frac{n(n+1)}{2} + n+1 = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2} $

Wnioski

Zauważmy, że skoro dla $n = 1$ teza jest spełniona to dla $n+1 = 2$ też, skoro dla $n = 2$ teza jest spełniona to dla $n+1 = 3$ też, skoro dla $n = 3$ teza jest spełniona to dla $n+1 = 4$ też, ...

Wynika z tego, że dla wszystkich $ n \ge 1 $ teza jest spełniona!

Przykłady

Udowodnij, że dla każdej dodatniej liczby całkowitej $n$, $ \sum^{n}_{i=1} {i^2} = \frac{n(n+1)(2n+1)}{6} $.

Rozwiązanie:

Baza indukcyjna: dla $ n = 1 $, $ \sum^{n}_{i=1} {i^2} = \sum^{1}_{i=1} {i^2} = 1^2 = 1 = \frac{n(n+1)(2n+1)}{6} $.

Krok indukcyjny: zakładamy, że $ \sum^{n}_{i=1} {i^2} = \frac{n(n+1)(2n+1)}{6} $, więc $ \sum^{n+1}_{i=1} {i^2} = \sum^{n}_{i=1} {i^2} + (n+1)^2 = \frac{n(n+1)(2n+1)}{6} + (n+1)^2 = \frac{n(n+1)(2n+1) + 6(n+1)^2}{6} = \frac{(n+1)(2n^2+n + 6n+6)}{6} = \frac{(n+1)(n+2)(2n+3)}{6} $.
Udowodnij, że suma katów w $n$-kącie jest równa $180(n-2)$.

Rozwiązanie:

Baza indukcyjna: w trójkącie suma kątów wynosi $180 = 180 (3-2) = 180(n-2)$.

Krok indukcyjny: zakładamy, że suma kątów w $n$-kącie jest równa $180(n-2)$, wtedy suma kątów w $n+1$-kącie wynosi $180(n-2) + 180 = 180(n+1 - 2)$. Jest tak, ponieważ $n+1$-kąt składa się z trójkąta i $n$-kąta.

Zadania

Udowodnij, że $ \sum^{n}_{i=0}{a^i} = \frac{a^{n+1}-1}{a-1} $ dla każdego $ a \ge 2 $ i całkowitego $ n \ge 1$.

Rozwiązanie:

Baza indukcyjna: dla $n = 1$ teza jest spełniona: $ \sum^{1}_{i=0}{a^i} = 1+a = \frac{(a+1)(a-1)}{a-1} = \frac{a^2-1}{a-1} = \frac{a^{n+1}-1}{a-1} $

Krok indukcyjny: zakładamy, że dla $n$ teza jest spełniona, wtedy: $$ \sum^{n+1}_{i=0}{a^i} = \sum^{n}_{i=0}{a^i} + a^{n+1} = \frac{a^{n+1}-1}{a-1} + a^{n+1} = \frac{a^{n+1} - 1 + (a-1)a^{n+1}}{a-1} = \frac{a^{n+1}(1 + a-1) - 1}{a-1} = \frac{a^{n+1+1} - 1}{a-1} $$
W turnieju tenisowym uczestniczyło $n$ graczy. Każdy rozegrał z każdym innym jeden mecz; nie było remisów. Udowodnić, że istnieje taki gracz $A$, który każdego innego gracza $B$ pokonał bezpośrednio lub pośrednio, tzn. $A$ wygrał z $B$ lub $A$ pokonał pewnego zawodnika $C$, który wygrał pośrednio lub bezpośrednio z $B$.
Rozwiązanie:

Oznaczmy $n$ jako liczbę graczy.

Baza indukcyjna: dla $n = 1$ teza jest spełniona: jedyny gracz wygrał z wszystkimi pozostałymi, bo ich nie było.

Krok indukcyjny: zakładamy, że dla $n$ teza jest spełniona, wtedy teza dla $n+1$ też jest prawdziwa, ponieważ jeśli nie będzie dowolnego gracza $G$ to wśród reszty graczy będzie istniał opisany w treści zadania gracz $A$ - korzystamy z założenia indukcyjnego. Po dodaniu gracza $G$ musi on stoczyć pojedynek z graczem $A$. Istnieją dwie możliwości:
1. gracz $A$ wygrał z $G$ - wtedy nowym graczem $A'$ pozostaje gracz $A$, bo nadal zwyciężył nad wszystkimi pozostałymi graczami;
2. gracz $A$ przegrał z $G$ - wtedy nowym graczem $A'$ zostaje gracz $G$, bo zwyciężył on nad wszystkimi pozostałymi graczami - nad $A$ bezpośrednio, a nad pozostałymi pośrednio przez $A$.
Udowodnij, że $ \sum_{i=0}^n{i^3} = (\frac{n(n+1)}{2})^2 $ dla całkowitego $n \ge 0$.

Rozwiązanie:

Baza indukcyjna: dla $n = 0$ teza jest spełniona: $ \sum_{i=0}^0{i^3} = 0^3 = 0 = \frac{0(0+1)}{2} $.

Krok indukcyjny: zakładamy, że dla $n$ teza jest spełniona. Wtedy: $$ \sum_{i=0}^{n+1}{i^3} = \sum_{i=0}^n{i^3} + (n+1)^3 = (\frac{n(n+1)}{2})^2 + (n+1)^3 = \frac{n^2(n+1)^2}{4} + (n+1)(n+1)^2 = (n+1)^2 (\frac{n^2}{4} + n + 1) = $$ $$ = (n+1)^2 \cdot \frac{n^2 + 4n + 4}{4} = (n+1)^2 \cdot \frac{(n + 2)^2}{4} = (\frac{(n+1)(n+2)}{2})^2 $$
Udowodnij, że $ \sum_{i=0}^n{i^4} = \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30} $ dla każdego całkowitego $n \ge 0$.

Rozwiązanie:

Baza indukcyjna: dla $n = 0$ teza jest spełniona: $ \sum_{i=0}^0{i^4} = 0^4 = 0 = \frac{0 \cdot 1 \cdot 1 \cdot (-1)}{30} $.

Krok indukcyjny: zakładamy, że dla $n$ teza jest spełniona. Wtedy: $$ \sum_{i=0}^{n+1}{i^4} = \sum_{i=0}^n{i^4} + (n+1)^4 = \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30} + (n+1)^4 = \frac{ (n+1)(n(2n+1)(3n^2+3n-1) + 30(n+1)^3) }{30} $$ $$ n(2n+1)(3n^2+3n-1) + 30(n+1)^3 = (2n^2+n)(3n^2+3n-1) + 30n^3 + 90n^2 + 90n + 30 = 6n^4 + 6n^3-2n^2 + 3n^3 + 3n^2 - n + 30n^3 + 90n^2 + 90n + 30 = $$ $$ = 6n^4 + 39n^3 + 91n^2 + 89n + 30 = (6n^4 + 9n^3) + (30n^3 + 45n^2) + (46n^2 + 69n) + (20n + 30) = 3n^3(2n+3) + 15n^2(2n+3) + 23n(2n+3) + 10(2n+3) = $$ $$ = (2n+3)(3n^3 + 15n^2 + 23n + 10) = (2n+3)(3n^3 + 6n^2 + 9n^2 + 18n + 5n + 10) = (2n+3)(3n^2(n+2) + 9n(n+2) + 5(n+2)) = (n+2)(2n+3)(3n^2 + 9n + 5) = $$ $$ = (n+2)(2n+3)(3n^2+6n+3+3n+3-1) = (n+1+1)(2(n+1)+1)(3(n+1)^2+3(n+1)-1) $$
$$ \sum_{i=0}^{n+1}{i^4} = \frac{ (n+1)(n(2n+1)(3n^2+3n-1) + 30(n+1)^3) }{30} = \frac{ (n+1)(n+1+1)(2(n+1)+1)(3(n+1)^2+3(n+1)-1) }{30} $$
Udowodnij, że $ 11 \mid 2^{6n+1} + 3^{2n+2} $ dla każdego całkowitego $n \ge 0$.

Rozwiązanie:

Baza indukcyjna: dla $n = 0$ teza jest spełniona: $2^1 + 3^2 = 2 + 9 = 11$.

Krok indukcyjny: zakładamy, że dla $n$ teza jest spełniona. Wtedy: $$ 2^{6n+1} + 3^{2n+2} = 11x $$ $$ \frac{2^{6n+7}}{64} + \frac{3^{2n+4}}{9} = 11x $$ $$ \frac{9}{64} \cdot 2^{6n+7} + 3^{2n+4} = 9 \cdot 11 x $$ $$ 2^{6n+7} - \frac{64 - 9}{64} \cdot 2^{6n+7} + 3^{2n+4} = 9 \cdot 11 x $$ $$ 2^{6(n+1)+1} + 3^{2(n+1)+2} = 11 \cdot 9 x + 11 \cdot 5 \cdot 2^{6n+1} $$ $$ 11 \mid 2^{6(n+1)+1} + 3^{2(n+1)+2} $$
Udowodnij, że $ 3 \mid n^3 + 2n $ dla każdego całkowitego $n \ge 0$.

Rozwiązanie:

Baza indukcyjna: dla $n = 0$ teza jest spełniona: $0^3 + 2 \cdot 0 = 0$.

Krok indukcyjny: zakładamy, że dla $n$ teza jest spełniona. Wtedy: $$ 3 \mid n^3 + 2n $$ $$ (n+1)^3 + 2(n+1) = n^3 + 3n^2 + 3n + 1 + 2n + 2 = n^3 + 2n + 3n^2 + 3n + 3 = 3x $$
Udowodnij, że $ 6 \mid n^3 + 3n^2 + 2n $ dla każdego całkowitego $n \ge 0$.

Rozwiązanie:

Baza indukcyjna: dla $n = 0$ teza jest spełniona: $0^3 + 3 \cdot 0^2 + 3 \cdot 0 = 0$.

Krok indukcyjny: zakładamy, że dla $n$ teza jest spełniona. Wtedy: $$ 6 \mid n^3 + 3n^2 + 2n $$ $$ (n+1)^3 + 3(n+1)^2 + 2(n+1) = n^3 + 3n^2 + 3n + 1 + 3n^2 + 6n + 3 + 2n + 2 = n^3 + 3n^2 + 2n + 6n + 6 + 3n^2 + 3n = 6x + 3(n^2 + n) $$ $2 \mid n^2 + n$, ponieważ $ n^2 \equiv n \pmod{2} $, a zarówno suma dwóch liczb parzystych, jak i nieparzystych jest parzysta. $$ 6 \mid (n+1)^3 + 3(n+1)^2 + 2(n+1) $$
Udowodnij, że $ \sum_{i=1}^n{\frac{1}{\sqrt{i}}} > \sqrt{n} $ dla każdego całkowitego $n \ge 2$.

Rozwiązanie:

Baza indukcyjna: dla $n = 2$ teza jest spełniona: $ \frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} = 1 + \frac{\sqrt{2}}{2} > 1 + 0,7 > 1,5 > \sqrt{2} $.

Krok indukcyjny: zakładamy, że dla $n$ teza jest spełniona. Wtedy: $$ \sum_{i=1}^{n+1}{\frac{1}{\sqrt{i}}} = \sum_{i=1}^n{\frac{1}{\sqrt{i}}} + \frac{1}{\sqrt{n+1}} > \sqrt{n} + \frac{1}{\sqrt{n+1}} $$ Załużmy, że $ \sqrt{n} + \frac{1}{\sqrt{n+1}} < \sqrt{n+1} $. Wtedy: $$ n + \frac{2\sqrt{n}}{\sqrt{n+1}} + \frac{1}{n+1} < n+1 $$ $$ \frac{2\sqrt{n}}{\sqrt{n+1}} + \frac{1}{n+1} < 1 $$ $$ 1 > \frac{2\sqrt{n}}{\sqrt{n+1}} + \frac{1}{n+1} > \frac{2\sqrt{n}}{\sqrt{n+1}} $$ $$ \frac{2\sqrt{n}}{\sqrt{n+1}} < 1 $$ $$ \frac{4n}{n+1} < 1 $$ $$ 4n < n+1 $$ $$ 3n < 1 $$ Sprzeczność! Oznacza to, że $ \sqrt{n} + \frac{1}{\sqrt{n+1}} \ge \sqrt{n+1} $, czyli: $$ \sum_{i=1}^{n+1}{\frac{1}{\sqrt{i}}} > \sqrt{n} + \frac{1}{\sqrt{n+1}} \ge \sqrt{n+1} $$ $$ \sum_{i=1}^{n+1}{\frac{1}{\sqrt{i}}} > \sqrt{n+1} $$
Udowodnij, że $ 10 \mid 3^{4n+2}+1 $ dla każdego całkowitego $n \ge 0$.

Rozwiązanie:

Baza indukcyjna: dla $n = 0$ teza jest spełniona: $ 3^2+1 = 9+1 = 10 $.

Krok indukcyjny: zakładamy, że dla $n$ teza jest spełniona. Wtedy: $$ 3^{4(n+1) + 2} + 1 = 3^{4n+6} + 3^{4n+2} + 1 - 3^{4n+2} = 10x + 3^{4n+6} - 3^{4n+2} = 10x + 3^{4n+2} (3^4-1) = 10x + 80 \cdot 3^{4n+2} = 10y $$ $$ 10 \mid 3^{4(n+1) + 2} + 1 $$
Udowodnij, że $ \sum_{i=1}^n{\frac{1}{i^2}} < 2 - \frac{1}{n} $ dla każdego całkowitego $n \ge 2$.

Rozwiązanie:

Baza indukcyjna: dla $n = 2$ teza jest spełniona: $ 1,25 < 1,5 $.

Krok indukcyjny: zakładamy, że dla $n$ teza jest spełniona. Wtedy: $$ \sum_{i=1}^{n+1}{\frac{1}{i^2}} = \sum_{i=1}^n{\frac{1}{i^2}} + \frac{1}{(n+1)^2} < 2 - \frac{1}{n} + \frac{1}{(n+1)^2} $$ Załużmy, że $ 2 - \frac{1}{n} + \frac{1}{(n+1)^2} \ge 2 - \frac{1}{n+1} $. Wtedy: $$ -\frac{1}{n} + \frac{1}{(n+1)^2} \ge -\frac{1}{n+1} $$ $$ \frac{1}{(n+1)^2} + \frac{1}{n+1} \ge \frac{1}{n} $$ $$ \frac{1 + n+1}{(n+1)^2} \ge \frac{1}{n} $$ $$ \frac{n+2}{(n+1)^2} \ge \frac{1}{n} $$ $$ n^2 + 2n \ge n^2+2n+1 $$ Sprzeczność! Oznacza to, że $ 2 - \frac{1}{n} + \frac{1}{(n+1)^2} < 2 - \frac{1}{n+1} $, czyli: $$ \sum_{i=1}^{n+1}{\frac{1}{i^2}} < 2 - \frac{1}{n} + \frac{1}{(n+1)^2} < 2 - \frac{1}{n+1} $$ $$ \sum_{i=1}^{n+1}{\frac{1}{i^2}} < 2 - \frac{1}{n+1} $$