03. Indukcja matematyczna

Treści kształcenia. Celem zajęć jest zaprezentowanie studentom Zasady Indukcji Matematycznej wraz z pokazaniem zastosowań tej zasady w dowodzeniu rozmaitych twierdzeń matematycznych. Zajęcia mają również uświadomić studentom, że komputer może być pomocny w formułowaniu twierdzeń matematycznych oraz że za jego możliwości dowodowe są ograniczone: potrafi on co najwyżej zweryfikować prawdziwość niektórych zdań tylko w skończonej ilości przypadków.

Efekty kształcenia. Student potrafi zastosować Zasadę Indukcji Matematycznej do dowodzenia rozmaitych twierdzeń matematycznych.

Wstęp¶

Podczas nauki matematyki w szkole średniej poznaliśmy wiele wzorów, które następnie wykorzystywaliśmy do rozwiązywania zadań. Dla przykładu dowiedzieliśmy się, że aby obliczyć sumę pierwszych $n$ wyrazów ciągu arytmetycznego o pierwszym wyrazie $a_1$ i różnicy $r$ , trzeba skorzystać ze wzoru

s_n=\frac{2a_1+(n-1)r}{2}\cdot n.

Powiedziano nam również, że liczba wszystkich podzbiorów zbioru $n$ -elementowego (wliczając w to zbiór pusty i cały zbiór) jest równa $2^n$ . Bardzo rzadko (albo wcale) pokazywano nam jednak, skąd te wzory się wzięły i dlaczego są one prawdziwe. Celem tych materiałów jest omówienie, jak można samemu odkryć niektóre ze wzorów i twierdzeń matematycznych oraz w jaki sposób można je udowodnić.

Przykład: suma pierwszych $n$ liczb nieparzystych¶

Zastanówmy się, czy istnieje jakiś łatwy sposób na obliczenie sumy pierwszych $n$ liczb nieparzystych, innymi słowy spróbujmy poszukać wzoru, który opisuje, jak zachowuje się ciąg dany wzorem

s_n=\sum_{i=0}^{n-1}(2i+1).

Proste rachunki pokazują, że:

dla $n=1$ mamy $s_1=\sum_{i=0}^0(2i+1)=1$ ;

dla $n=2$ mamy $s_2=\sum_{i=0}^1(2i+1)=1+3=4$ ;

dla $n=3$ mamy $s_3=\sum_{i=0}^2(2i+1)=1+3+5=9$ ;

dla $n=4$ mamy $s_4=\sum_{i=0}^3(2i+1)=1+3+5+7=16$ ;

dla $n=5$ mamy $s_5=\sum_{i=0}^4(2i+1)=1+3+5+7+9=25$ .

Powyższe proste rachunki zdają się sugerować, że dla każdego $n\in\mathbb{N}$ prawdziwa jest równość

s_n=n^2.

Spróbujmy potwierdzić nasze przypuszczenia w “większej” liczbie przypadków.

def sum_first_n_odd(n):
    # suma pierwszych n liczb nieparzystych 
    s=0 # początkowo suma jest rowna 0
    for i in range(n): # dla i z zakresu od 0 do i-1
        s += 2*i+1 # do sumy dodajemy 2i+1
    return s
sum_first_n_odd(10)

100

N = 10**4 # sprawdzamy prawdziwość naszej tezy aż do N włącznie

for i in range(N): # sprawdzamy czy dla którejść z liczb i od 0 do N-1 
    if sum_first_n_odd(i) != i**2: # suma pierwszszych i liczb nieparzystych jest różna od i^2.
        test = False 
        break
    else:
        test = True

if test == True:
    print('Dla wszystkich n mniejszych bądź równych niż', N, 'nasza równość jest prawdziwa.')   
else:
    print('Nasze przypuszczenie jest błędne')

Dla wszystkich n mniejszych bądź równych niż 10000 nasza równość jest prawdziwa.

Ważne: w powyższy sposób jesteśmy w stanie sprawdzić za pomocą komputera prawdziwość naszej tezy tylko dla skończonej liczby przypadków. Aby potwierdzić, że nasze przypuszczenie jest prawdziwe dla wszystkich liczb naturalnych, będziemy potrzebowali bardzo ważnego twierdzenia zwanego Zasadą Indukcji Matematycznej (twierdzenie to wynika bezpośrednio z tego, jak konstruuje się zbiór liczb naturalnych).

Zasada indukcji matematycznej¶

Niech $A$ będzie podzbiorem zbioru liczb naturalnych $\mathbb{N}$ . Jeśli spełnione są warunki:
$1\in A$ ;
dla każdego $n\in\mathbb{N}$ : jeśli $n\in A$ , to $n+1\in A$ ;

to $A=\mathbb{N}$ .

Uwaga: Zasadę Indukcji Matematycznej można wysłowić w następujący równoważny sposób.

Zasada indukcji Matematycznej
Niech dla każdego $n\in\mathbb{N}$ będzie dane zdanie $T(n)$ . Jeśli spełnione są warunki:
zdanie T(1) jest prawdziwe;
dla każdego $n\in\mathbb{N}$ z prawdziwości zdania $T(n)$ wynika prawdziwość zdania $T(n+1)$ ;

to zdanie $T(n)$ jest prawdziwe dla wszystkich liczb naturalnych.

Przykład: suma pierwszych $n$ liczb nieparzystych - cd.¶

Wyposażeni w Zasadę Indukcji Matematycznej, wracamy do naszego przykładu. Aby potwierdzić nasze przypuszczenie, musimy pokazać, że zbiór

A:=\{n\in\mathbb{N}\colon \sum_{i=0}^{n-1}(2i+1)=n^2\}

jest w istocie równy $\mathbb{N}$ . W tym celu zastosujemy poznaną przed chwilą zasadę.

Sprawdziliśmy już, że $1\in A$ . W sumie to sprawdziliśmy dużo więcej: pokazaliśmy, że $\{1,2,\ldots,1000\}\subset A$ .
Pokażemy teraz, że dla dowolnej liczby naturalnej $n$ : jeśli $n\in A$ , to $n+1\in A$ .

Przypuśćmy zatem, że liczba naturalna $n$ należy do zbioru $A$ . Oznacza to, że

\sum_{i=0}^{n-1}(2i+1)=n^2.\quad\quad(1)

Korzystając z tego faktu musimy pokazać, że liczba $n+1$ również należy do zbioru $A$ . Chcemy pokazać zatem, że

\sum_{i=0}^{n}(2i+1)=(n+1)^2.

Mamy

\sum_{i=0}^{n}(2i+1)=\sum_{i=0}^{n-1}(2i+1)+(2n+1).

Korzystając z równości $(1)$ otrzymujemy, że

\sum_{i=0}^{n}(2i+1)=n^2+(2n+1)=(n+1)^2.

To oznacza, że $n+1\in A$ .

Na mocy Zasady Indukcji Matematycznej mamy $A=\mathbb{N}$ .

Przykład: liczba podzbiorów¶

Postaramy się teraz zrozumieć, ile jest wszystkich podzbiorów zbioru $n$ -elementowego (wliczając w to zbiór pusty i cały zbiór).

Podzbiorami zbioru jednoelementowego $\{a\}$ są $\emptyset$ i $\{a\}$ . Jest ich zatem: 2.

Podzbiorami zbioru dwuelementowego $\{a,b\}$ są $\emptyset$ , $\{a\}$ , $\{b\}$ oraz $\{a,b\}$ . Jest ich zatem: 4.

Podzbiorami zbioru trzyelementowego $\{a,b,c\}$ są $\emptyset$ , $\{a\}$ , $\{b\}$ , $\{c\}$ , $\{a,b\}$ , $\{a,c\}$ , $\{b,c\}$ oraz $\{a,b,c\}$ . Jest ich zatem: 8.

def power_set(set):
    # returns a list of all subsets of a set (given as a list)
    if (len(set) == 0): # jedynym podzbiorem zbioru pustego jest zbiór pusty
        return [[]]
    else:
        all_subsets = [ ] # aby wygenerować podzbiory zboru n elementowego zauważamy, że podziory te dzielą się na dwie klasy: 
                          # te które zawieają ustalony element x i te które go nie zawierają. To pozwala wszystkie podzbiory wyznaczyć rekurencyjnie.
        for small_subset in power_set(set[1:]):
            all_subsets += [small_subset]
            all_subsets += [[set[0]] + small_subset]
        return all_subsets
print(power_set(range(5)))
print(len(power_set(range(10))))

[[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2], [3], [0, 3], [1, 3], [0, 1, 3], [2, 3], [0, 2, 3], [1, 2, 3], [0, 1, 2, 3], [4], [0, 4], [1, 4], [0, 1, 4], [2, 4], [0, 2, 4], [1, 2, 4], [0, 1, 2, 4], [3, 4], [0, 3, 4], [1, 3, 4], [0, 1, 3, 4], [2, 3, 4], [0, 2, 3, 4], [1, 2, 3, 4], [0, 1, 2, 3, 4]]
1024

Powyższe wyniki sugerują, że liczba podzbiorów zbioru $n$ -elementowego jest równa $2^n$ . Niech więc $T(n)$ oznacza zdanie: liczba podzbiorów dowolnego zbioru $n$ -elementowego jest równa $2^n$ .

Sprawdziliśmy już, że zdanie $T(1)$ jest prawdziwe.
Pokażemy teraz, że dla każdego $n\in\mathbb{N}$ z prawdziwości zdania $T(n)$ wynika prawdziwość zdania $T(n+1)$ ;

Przypuśćmy zatem, że zdanie $T(n)$ jest prawdziwe dla pewnego $n$ . Korzystając z tego założenia musimy pokazać, że liczba podzbiorów dowolnego zbioru $n+1$ -elementowego jest równa $2^{n+1}$ . Niech więc $B$ będzie dowolnym zbiorem $n+1$ -elementowym i niech $x\in B$ .

Rodzina tych podzbiorów zbioru $B$ , które nie zawierają $x$ , jest taka sama jak rodzina wszystkich podzbiorów zbioru $B\setminus\{x\}$ . Zatem podzbiorów zbioru $B$ , które nie zawierają $x$ , jest dokładnie $2^n$ (zbiór $B\setminus\{x\}$ jest $n$ -elementowy).
Aby utworzyć rodzinę tych podzbiorów zbioru $B$ , które zawierają $x$ , wystarczy utworzyć rodzinę wszystkich podzbiorów zbioru $B\setminus\{x\}$ a następnie do każdego elementu tej rodziny dołożyć $x$ . Zatem podzbiorów zbioru $B$ , które zawierają $x$ , jest dokładnie $2^n$ .

Zatem wszystkich podzbiorów zbioru $B$ jest dokładnie $2^n+2^n=2^{n+1}$ .

Na mocy Zasady Indukcji Matematycznej otrzymujemy, że liczba podzbiorów dowolnego zbioru $n$ -elementowego jest równa $2^n$ .

Przykład: wieże Hanoi¶

Mamy trzy paliki (nazwijmy je palikiem A, palikiem B i palikiem C) i $n$ krążków o różnych średnicach, które w chwili początkowej znajdują się na paliku A w kolejności od największego (ten jest na dole) do najmniejszego. Chcemy przenieść wszystkie krążki z palika A na palik C zgodnie z dwoma regułami:

krążek o średnicy większej nie może być położony na krążek o średnicy mniejszej;
w każdym ruchu możemy zdjąć tylko jeden krążek i nałożyć go na inny palik.

Naszym zadaniem jest przeniesienie wszystkich krążków na palik C używając do tego minimalnej ilości ruchów. Oznaczmy tę liczbę ruchów przez $H(n)$ .

Jest jasne, że $H(1)=1$ i nietrudno sprawdzić, że $H(2)=3$ .
Załóżmy teraz, że znamy już sposób na optymalne rozwiązanie naszego zadania dla pewnego $n$ . Aby rozwiązać zadanie dla $n+1$ krążków, możemy postąpić następująco:
przenosimy $n$ krążków z palika A na palik B wykonując przy tym $H(n)$ ruchów;
przenosimy największy krążek z palika A na palik C;
przenosimy krążki z palika B na palik C wykonując przy tym $H(n)$ ruchów.

Powyższy algorytm pokazuje, że $H(n+1)\leq 2H(n)+1$ . Z drugiej strony największy krążek musi być przeniesiony co najmniej raz; tuż przed jego pierwszym ruchem wszystkie $n$ mniejszych krążków muszą leżeć na trzecim paliku (innym niż palik A i palik, na który kładziemy największy krążek), więc musieliśmy wcześniej wykonać co najmniej $H(n)$ ruchów, a po jego ostatnim ruchu (na palik C) trzeba je jeszcze przenieść na palik C, wykonując znów co najmniej $H(n)$ ruchów. Stąd $H(n+1)\geq 2H(n)+1$ , czyli optymalna liczba ruchów potrzebna do przeniesienia $n+1$ krążków jest równa $2H(n)+1$ .

Ponieważ $n$ było dowolne, pokazaliśmy zatem, że dla każdego $n\in\mathbb{N}$ mamy

H(n+1)=2H(n)+1.

Jest to tak zwana rekurencyjna definicja ciągu: podaliśmy, ile jest równy pierwszy wyraz ciągu i podaliśmy regułę, jak wyznaczyć kolejne wyrazy ciągu, jeśli znamy już poprzednie. Więcej o ciągach rekurencyjnych będzie powiedziane przy okazji omawiania ciągów.

Czy jesteśmy w stanie podać jawny wzór na liczbę $H(n)$ ?

def H(n):
    # minimalna liczba ruchów
    if n > 1:
        return 2*H(n-1)+1
    else:
        return 1
for i in range(10):
    print(H(i+1))

Powyższe obliczenia sugerują nam, że dla każdego $n\in\mathbb{N}$ mamy

H(n)=2^n-1.

Udowodnimy to stosując zasadę indukcji matematycznej.

Wiemy, że $H(1)=1$ , wzór ten jest więc prawdziwy dla $n=1$ .
Załóżmy teraz, że dla pewnego $n$ wiemy już, że $H(n)=2^{n}-1$ . Musimy pokazać, że $H(n+1)=2^{n+1}-1$ . Mamy (korzystając z pokazanych już własności ciągu $H(n)$

H(n+1)=2H(n)+1=2(2^n-1)+1=2^{n+1}-1.

To kończy dowód indukcyjny.

Przykład: nierówność Bernoulliego¶

Pokażemy teraz, że dla każdego $n\in\mathbb{N}$ i $x\geq -1$ mamy

(1+x)^n\geq 1+nx.

W tym celu zastosujemy zasadę indukcji matematycznej.

Dla $n=1$ nierówność jest oczywiście prawdziwa (w istocie mamy równość).
Załóżmy teraz, że dla pewnego $n$ nierówność

(1+x)^n\geq 1+nx

jest spełniona dla wszystkich $x\geq -1$ . Musimy pokazać, że dla wszystkich $x\geq -1$ mamy

(1+x)^{n+1}\geq 1+(n+1)x.

Mnożąc obustronnie strony pierwszej z powyższych nierówności przez (nieujemną!) liczbę (1+x) dostajemy, że

(1+x)^{n+1}\geq (1+nx)(1+x)=1+(n+1)x+nx^2.

Ale oczywiście

1+(n+1)x+nx^2\geq 1+(n+1)x

więc dla wszystkich $x\geq -1$ mamy

(1+x)^{n+1}\geq 1+(n+1)x.

To kończy dowód indukcyjny.

Uwaga: nierówność Bernoulliego okaże się niezwykle przydatna na Analizie Matematycznej.

Przykład: nierówność między średnią geometryczną a arytmetyczną¶

Pokażemy, że dla dowolnej liczby naturalnej $n\geq 2$ prawdziwe jest zdanie $T(n)$ : jeśli iloczyn $n$ liczb dodatnich $x_1,x_2,\ldots,x_n$ jest równy 1, to ich suma jest większa bądź równa niż $n$ .

W tym celu zastosujemy Zasadę Indukcji Matematycznej.

Najpierw pokażemy, że zdanie $T(2)$ jest prawdziwe. Musimy pokazać zatem, że jeśli dla liczb dodatnich $x_1$ i $x_2$ mamy

x_1\cdot x_2=1,

to

x_1+x_2\geq 2.

Ponieważ

x_1=\frac{1}{x_2},

to wystarczy uzasadnić, że dla dowolnej liczby dodatniej $x_2$ mamy

x_2+\frac{1}{x_2}\geq 2.

Ale powyższa nierówność jest równoważna (mnożymy ją obustronnie przez $x_2$ i przenosimy wszystko na lewą stronę) nierówności,

(x_2-1)^2\geq 0,

która jest prawdziwa.

Załóżmy teraz, że dla pewnego $n\geq 2$ zdanie $T(n)$ jest prawdziwe. Pokażemy, że prawdziwe jest zdanie $T(n+1)$ . Niech więc $x_1,\ldots, x_n,x_{n+1}$ będą dodatnimi liczbami takimi, że

x_1\cdot\ldots\cdot x_n\cdot x_{n+1}=1.

Musimy pokazać, że

x_1+\ldots+ x_n+ x_{n+1}\geq {n+1}.

Jest jasne, że któraś spośród liczb $x_1,\ldots, x_n,x_{n+1}$ jest większa bądź równa od 1 (gdyby wszystkie były mniejsze niż jeden, to ich iloczyn byłby mniejszy niż jeden) i któraś jest mniejsza bądź równa niż 1 (gdyby wszystkie były większe niż jeden, to ich iloczyn byłby większy niż jeden). Możemy założyć zatem (ewentualnie zmieniając kolejności naszych danych liczb), że $x_n\geq 1$ i $x_{n+1}\leq 1$ . Niech teraz $y_i=x_i$ dla $i=1,\ldots, n-1$ i $y_n=x_n\cdot x_{n+1}$ . Ponieważ iloczyn $n$ liczb dodatnich $y_1,y_2,\ldots,y_n$ jest równy 1, to z naszego założenia wynika, że ich suma jest większa bądź równa niż $n$ . Mamy

x_1+\ldots+ x_n+ x_{n+1}=y_1+\ldots+ y_n-x_n\cdot x_{n+1}+x_n+x_{n+1}-1+1=y_1+\ldots+ y_n+(1-x_n)( x_{n+1}-1)+1\geq n+1,

gdzie ostatnia nierówność wynika z faktu, że $(1-x_n)( x_{n+1}-1)\geq 0$ .

Wniosek

Niech $x_1,\ldots, x_n$ będą liczbami dodatnimi. Niech ponadto dla $i=1,\ldots, n$

y_i=\frac{x_i}{\sqrt[n]{x_1\cdot\ldots \cdot x_n}}.

Iloczyn liczb $y_1,y_2,\ldots,y_n$ jest równy 1, zatem na mocy powyższego przykładu ich suma jest większa bądź równa niż $n$ . Zatem

\frac{x_1}{\sqrt[n]{x_1\cdot\ldots \cdot x_n}}+\ldots+\frac{x_n}{\sqrt[n]{x_1\cdot\ldots \cdot x_n}} \geq n.

Mnożąc obustronnie powyższą nierówność przez $\sqrt[n]{x_1\cdot\ldots \cdot x_n}$ i dzieląc obustronnie przez $n$ otrzymujemy, że

\sqrt[n]{x_1\cdot\ldots \cdot x_n}\leq \frac{x_1+\ldots+ x_n}{n}.

Udowodniliśmy więc, że średnia geometryczna $n$ liczb jest mniejsza bądź równa od ich średniej arytmetycznej.

Przykład: niepoprawny dowód indukcyjny¶

Zachowaj ostrożność!!!

Pokażemy teraz, że wszystkie koty są tego samego koloru. By to zrobić, wystarczy pokazać, że dla każdego $n\in\mathbb{N}$ prawdziwe jest zdanie $T(n)$ : w dowolnym zbiorze złożonym z $n$ kotów wszystkie koty są tego samego koloru.

Zdanie $T(1)$ jest w sposób oczywisty prawdziwe.
Załóżmy teraz, że dla pewnego $n$ prawdziwe jest zdanie $T(n)$ . Pokażemy, że prawdziwe jest zdanie $T(n+1)$ . Niech więc $A$ będzie zbiorem złożonym z $n+1$ kotów. Wyrzucając z $A$ pewnego kota $x_1$ otrzymamy zbiór zawierający n kotów zatem z założenia wszystkie koty poza kotem $x_1$ są tego samego koloru. Ale wyrzucając teraz z $A$ kota $x_2$ (innego niż $x_1$ ) znowu otrzymamy zbiór zawierający n kotów, w tym kota $x_1$ . Zatem kot $x_1$ ma taki sam kolor jak pozostałe koty w zbiorze $A$ . Stąd w zbiorze $A$ wszystkie koty mają ten sam kolor.

Na mocy indukcji zdanie $T(n)$ jest prawdziwe dla wszystkich $n$ . Wszystkie koty są więc tego samego koloru.

Do samodzielnego przestudiowania¶

Przykład: suma kwadratów¶

Pokażemy, że dla każdego $n\in\mathbb{N}$ mamy

\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}.

Zastosujemy zasadę indukcji matematycznej.

Dla n=1 mamy:

\sum_{i=1}^1i^2=1 \text{ oraz }\frac{1(1+1)(2+1)}{6}=1,

równość jest zatem w tym przypadku prawdziwa.

Załóżmy teraz, że dla pewnego $n\in\mathbb{N}$ mamy

\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}.

(1)

Musimy pokazać, że

\sum_{i=1}^{n+1} i^2=\frac{(n+1)(n+2)(2n+3)}{6}.

Korzystając z założenia i wykonując proste rachunki dostajemy

\sum_{i=1}^{n+1}i^2=\sum_{i=1}^{n}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+7n+6)}{6}=\frac{(n+1)(n+2)(2n+3)}{6}.

A dokładnie tyle chcieliśmy pokazać.

Przykład nr 1 do samodzielnego rozwiązania¶

Pokaż, że dla każdego $n\in\mathbb{N}$ mamy

\sum_{i=1}^n\frac{1}{i(i+1)}=\frac{n}{n+1}.

Czy potrafisz udowodnić to bez użycia indukcji?

Przykład nr 2 do samodzielnego rozwiązania¶

Pokaż, że dla każdego $n\in\mathbb{N}$ mamy

\sum_{i=1}^{2n}i=n(2n+1).

Przykład: suma ciągu geometrycznego¶

Pokażemy, że dla każdego $n\in\mathbb{N}$ i każdego $x\not=1$ mamy

\sum_{i=0}^nx^i=\frac{x^{n+1}-1}{x-1}.

Zastosujemy zasadę indukcji matematycznej.

Mamy

\sum_{i=0}^1x^i=1+x

oraz

\frac{x^2-1}{x-1}=\frac{(x-1)(x+1)}{x-1}=x+1,

nasza równość jest więc prawdziwa dla $n=1$ .

Załóżmy teraz, że dla pewnego $n\in\mathbb{N}$ mamy

\sum_{i=0}^nx^i=\frac{x^{n+1}-1}{x-1}.

Pokażemy, że

\sum_{i=0}^{n+1}x^i=\frac{x^{n+2}-1}{x-1}.

Mamy

\sum_{i=0}^{n+1}x^i=\sum_{i=0}^{n}x^i+x^{n+1}=\frac{x^{n+1}-1}{x-1}+x^{n+1}=\frac{x^{n+1}-1+x^{n+2}-x^{n+1}}{x-1}=\frac{x^{n+2}-1}{x-1}.

A dokładnie tyle chcieliśmy pokazać.

Przykład: suma odwrotności kwadratów¶

Pokażemy, że dla każdego $n\in\mathbb{N}$ mamy

\sum_{i=1}^n\frac{1}{i^2}\leq 2-\frac{1}{n}.

Uwaga: później na analizie dowiemy się, że oznacza to, że szereg nieskończony $\sum_{i=1}^\infty\frac{1}{i^2}$ jest zbieżny.

Dla $n=1$ nasza nierówność jest w istocie równością.
Załóżmy, że dla pewnego $n\in\mathbb{N}$ mamy, że

\sum_{i=1}^n\frac{1}{i^2}\leq 2-\frac{1}{n}.

Aby zastosować Zasadę Indukcji, musimy uzasadnić, że

\sum_{i=1}^{n+1}\frac{1}{i^2}\leq 2-\frac{1}{n+1}.

Mamy

\sum_{i=1}^{n+1}\frac{1}{i^2}=\sum_{i=1}^n\frac{1}{i^2}+\frac{1}{(n+1)^2}.

Na mocy założenia otrzymujemy więc, że

\sum_{i=1}^{n+1}\frac{1}{i^2}\leq 2-\frac{1}{n}+\frac{1}{(n+1)^2}.

Aby zakończyć dowód, wystarczy uzasadnić zatem, że dla dowolnej liczby naturalnej $n$ mamy, że

2-\frac{1}{n}+\frac{1}{(n+1)^2}\leq 2-\frac{1}{n+1}.

Proste rachunki (wszystko na lewą stronę i wspólny mianownik) pokazują, że nierówność ta jest równoważna nierówności

\frac{-1}{n(n+1)^2}\leq 0.

która oczywiście jest prawdziwa.

Przykład nr 3 do samodzielnego rozwiązania¶

Pokaż, że dla każdego $n\in\mathbb{N}$ mamy

\sum_{i=1}^n\frac{1}{\sqrt{i}}\geq\sqrt{n}.

Uwaga: później na analizie dowiemy się, że oznacza to, że szereg nieskończony $\sum_{i=1}^\infty\frac{1}{\sqrt{i}}$ jest rozbieżny.

Przykład nr 4 do samodzielnego rozwiązania¶

Dany jest ciąg $(a_n)$ taki, że

$a_1=1$ ;
$a_{n+1}=a_n+{n+1}$ .

Pokaż, że dla każdego $n\in\mathbb{N}$ mamy

a_n=\frac{n^2+n}{2}.

Przykład nr 5 do samodzielnego rozwiązania¶

Połączono $n$ punktów strzałkami w taki sposób, że każda para różnych punktów jest połączona strzałką. Udowodnij, że istnieje ``centrum’'czyli punkt, z którego można dojść do każdego innego w co najwyżej dwóch krokach, idąc zgodnie z kierunkiem strzałek.

Literatura¶

J. Banaś, S. Wędrychowicz, Zbiór zadań z analizy matematycznej

Wstęp¶

Przykład: suma pierwszych nnn liczb nieparzystych¶

Zasada indukcji matematycznej¶

Przykład: suma pierwszych nnn liczb nieparzystych - cd.¶

Przykład: liczba podzbiorów¶

Przykład: wieże Hanoi¶

Przykład: nierówność Bernoulliego¶

Przykład: nierówność między średnią geometryczną a arytmetyczną¶

Przykład: niepoprawny dowód indukcyjny¶

Do samodzielnego przestudiowania¶

Przykład: suma kwadratów¶

Przykład nr 1 do samodzielnego rozwiązania¶

Przykład nr 2 do samodzielnego rozwiązania¶

Przykład: suma ciągu geometrycznego¶

Przykład: suma odwrotności kwadratów¶

Przykład nr 3 do samodzielnego rozwiązania¶

Przykład nr 4 do samodzielnego rozwiązania¶

Przykład nr 5 do samodzielnego rozwiązania¶

Literatura¶

Przykład: suma pierwszych $n$ liczb nieparzystych¶

Przykład: suma pierwszych $n$ liczb nieparzystych - cd.¶