03. Indukcja matematyczna#

Tresci 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ć pomocy 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óbumy 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 wszyskich liczb naturalnych będziemy potrzebowali bardzo ważnego twierdzenie 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 nastepują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 przypuszcenie 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 podzioró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 podziorów zbioru \(B\), które nie zawierają \(x\) jest taka sama jak rodzina wszystkkich podzioró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 podziorów zbioru \(B\), które zawierają \(x\) wystarczy utworzyć rodzinę wszystkkich podzioró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ść wszyskie 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śći 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 na optymalne rozwiązanie naszego zadania dla pewnego \(n\). Aby rozwiązać zadanie dla \(n+1\) krążków możemy postąpić nastepują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 (i chwila zastanowienia) pokazuje, że optymalna liczba ruchów potrzebna do przeniesienia \(n+1\) krążków jest równa \(2H(n)+1\).

Na mocy Zasady Indukcji Matematycznej 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: podalismy 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))

1
3
7
15
31
63
127
255
511
1023

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ąć 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 wszyskich \(x\geq -1\). Musimy pokazać, że dla wszystich \(x\geq -1\) mamy

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

Mnożąc obustronnie strony piewszej 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 wszystich \(x\geq -1\) mamy

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

To kończy dowód indukcyjny.

Uwaga: nierówność Bernouliego 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łoż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ś z poś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 wszyskie 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żonych z \(n\) kotów wszystkie koty sa tego samego koloru.

  • Zdanie \(T(1)\) jest w sposób oczywisty prawdziwe.

  • Założ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 \begin{equation} \sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}. \end{equation} 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 wsyatrczy 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{n}}\) 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 kazdego 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