Wykaż, że suma jest ograniczona z góry przez stałą

[JumpSmerf]

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).

[bzyk12]

\(\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.

[pyzol]

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ć...

[Nakahed90]

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

[pyzol]

Ano fakt

[JumpSmerf]

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.

[smigol]

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.

[JumpSmerf]

\(\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.

[smigol]

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