Matematyka.pl

Witam.
Nie jestem pewien rozwiązania zadania z książki Cormena, Leisersona, Rivesta i Steina "Wprowadzenie do algorytmów".

Mianowicie jest to następujące zadanie:
Wykaż, że suma \(\displaystyle{ \sum_{k=1}^{n} 1/k^{2}}\) jest ograniczona z góry przez stałą.

Postanowiłem zrobić to zadanie przez indukcję, mianowicie (c to stała):
\(\displaystyle{ \sum_{k=1}^{n+1} 1/k^{2} = \sum_{k=1}^{n} 1/k^{2} + 1/(n+1)^{2} \le c + 1/(n+1)^{2} = c(1 + \frac{1}{(n+1)^{2}c}) \le c + 1}\)

Niestety wydaje mi się, że powinno być na końcu \(\displaystyle{ \le c}\). Zrobiłem jak autorzy w jednym z przykładów, ale u nich na końcu wyrażenie w nawiasie było mniejsze od \(\displaystyle{ 1}\), a u mnie tego nie ma.

Proszę o podpowiedź co źle robię (jeżeli jest źle).

\(\displaystyle{ \sum_{k=1}^{\infty} \frac{1}{k^2}= \frac{\pi^2}{6}}\)

ciąg sum częściowych jest ciągiem rosnącym, jego granica istnieje, więc masz ograniczenie z góry.

Nie licząc pierwszego wyrazu, to jeden z peirwszych dowodów na analizie (co do szeregów)
\(\displaystyle{ \sum\frac{1}{n^2} \le \sum \frac{1}{n(n-1)}=\sum \left( \frac{1}{n-1}-\frac{1}{n}\right)}\)
Te ostanie łatwo się da wyliczyć...

Jak dla mnie to nie ma co tu pokazywać. Każda skończona suma jest ograniczona.

Ano fakt

Nakahed90 pisze:Jak dla mnie to nie ma co tu pokazywać. Każda skończona suma jest ograniczona.

Ale w tym zadaniu trzeba wykazać to, że istnieje jedna stała, która niezależnie od tego, co podstawimy za n, to i tak wyjdzie liczba mniejsza od stałej. Więc chyba nie wszystkie sumy skończone są ograniczone co do stałej, jak w tym przypadku: \(\displaystyle{ \sum_{k=1}^{n} 1/k^{2} = O(1)}\). Chociaż pewnie się mylę - z analizy jeszcze nie umiem zbyt dużo, bo w liceum miałem tego niewiele.

Głównie chciałem się dowiedzieć, czy ten mój dowód jest poprawny, bo nie byłem pewien. Chociaż i tak dopiero teraz zauważyłem, że jest to szereg geometryczny, więc wystarczy normalnie policzyć, ale i tak nie o to chodzi, bo nie chciałem liczyć "na pałę" ze wzorów.

Twój dowód nie jest poprawny.
\(\displaystyle{ \sum_{k=1}^{n} 1/k^{2}}\) nie jest szeregiem geometrycznym, chociażby dlatego, że nie mamy tu żadnego szeregu. Nie jest to też suma ciągu geometrycznego.

\(\displaystyle{ \sum_{k=1}^{n} 1/k^{2}}\) nie jest szeregiem geometrycznym, chociażby dlatego, że nie mamy tu żadnego szeregu. Nie jest to też suma ciągu geometrycznego.

No tak, jasne faktycznie mi się tu pomyliło.

Możesz to udowodnić nieindukcyjnie zauważając, że \(\displaystyle{ \frac{1}{k^2} < \frac{1}{k(k-1)}}\).