Suma kwadratów liczb naturalnych

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
XYZmat
Użytkownik
Użytkownik
Posty: 142
Rejestracja: 1 wrz 2017, o 11:39
Płeć: Kobieta

Suma kwadratów liczb naturalnych

Post autor: XYZmat » 1 kwie 2018, o 21:10

W jaki sposób wyznaczyć wzór na \(\displaystyle{ 1^2+2^2+3^2+...+n^2}\) ? Wiem, że rozwiązaniem jest \(\displaystyle{ \frac{n(n+1)(2n+1)}{6}}\) oraz, że gdybym miała z góry podaną tą równość i zadanie polegałoby na udowodnieniu jej to posłużyłaby mi do tego indukcja, ale interesuje mnie w jaki sposób obliczyć takie wyrażenie bez jakichkolwiek wskazówek.

rubiccube
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 4 sty 2017, o 20:36
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 2 razy
Pomógł: 4 razy

Suma kwadratów liczb naturalnych

Post autor: rubiccube » 1 kwie 2018, o 21:18


michcior
Użytkownik
Użytkownik
Posty: 32
Rejestracja: 9 mar 2016, o 16:28
Płeć: Mężczyzna
Lokalizacja: Warszawa

Suma kwadratów liczb naturalnych

Post autor: michcior » 2 kwie 2018, o 12:36

Takie rzeczy można też pokazywać za pomocą bijekcji miedzy odpowiednimi zbiorami,a następnie skorzystania z równości mocy zbiorów. Nie będę tłumaczył czegoś co rozumiem połowicznie, przykład ktory został tu juz przytoczony oraz kombinatoryczny dowód równości można znaleźć na stronie https://www.mimuw.edu.pl/~guzicki/komb.html w 1-szym linku

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15009
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 145 razy
Pomógł: 4974 razy

Re: Suma kwadratów liczb naturalnych

Post autor: Premislav » 2 kwie 2018, o 14:29

Bijekcje mi się nigdy nie podobały (takie metody uważałem za z kapelusza wzięte i nawet się irytowałem, widząc ich zastosowanie), natomiast tak mi się właśnie przypomniało, że ostatnio dowodziłem taką rzecz: 430464.htm

No to jak się przyjrzymy tej (udowodniłem tam coś ogólniejszego) formule
\(\displaystyle{ sum^{n}_{k=2} {k choose 2} = {n+1 choose 3}}\)
to po skorzystaniu z: \(\displaystyle{ {k choose 2}=frac{k(k-1)}{2}}\)
i rozbiciu na dwie sumy otrzymujemy:
\(\displaystyle{ frac 1 2 sum_{k=2}^{n}k^2-frac 1 2 sum_{k=2}^{n}k={n+1 choose 3}}\)
a ponieważ \(\displaystyle{ 1^2=1}\), więc równie dobrze możemy zapisać
\(\displaystyle{ frac 1 2 sum_{k=1}^{n}k^2-frac 1 2 sum_{k=1}^{n}k={n+1 choose 3}}\)
czyli
\(\displaystyle{ sum_{k=1}^{n}k^2=2{n+1 choose 3}+ sum_{k=1}^{n}k}\)
Tę ostatnią sumę zwijamy ze wzoru na sumę wyrazów ciągu arytmetycznego i jest:
\(\displaystyle{ sum_{k=1}^{n}k^2=2{n+1 choose 3}+ frac{n(n+1)}{2}=\= frac{(n+1)n(2n-2)+3n(n+1)}{6}= frac{n(n+1)(2n+1)}{6}}\)

Ale to nie jest zbyt odkrywcza myśl z mojej strony, bo chyba gdzieś rozmawiałem o takiej możliwości z userem Janusz Tracz,.

Elayne
Użytkownik
Użytkownik
Posty: 802
Rejestracja: 24 paź 2011, o 01:24
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 61 razy
Pomógł: 248 razy

Suma kwadratów liczb naturalnych

Post autor: Elayne » 2 kwie 2018, o 16:05

Aryabhata przedstawił elegancki sposób dojścia do tego.
The Aryabhatiya of Aryabhata

Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 2942
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 72 razy
Pomógł: 977 razy

Re: Suma kwadratów liczb naturalnych

Post autor: Janusz Tracz » 2 kwie 2018, o 19:14

Dość prosty dowód to zauważenie że zachodzi dla dowolnego \(\displaystyle{ k=0,1,2,3,...,n}\) równość \(\displaystyle{ (k+1)^3-k^3=3k^2+3k+1}\). Sumując tą równość stronami lewa strona teleskopuje się a prawą stronę rozpiszemy na sumę sum z czego jedna będzie szukaną sumą kwadratów. Mamy więc

\(\displaystyle{ \sum_{k=0}^{n}\left[ (k+1)^3-k^3\right] =\sum_{k=0}^{n}\left[ 3k^2+3k+1\right]}\)

\(\displaystyle{ (n+1)^3=3{\red{\sum_{k=0}^{n}k^2}}+ \frac{(n+1)(3n+2)}{2}}\)

po rutynowych przekształceniach dostajemy oczekiwany wynik bez jego wcześniejszej znajomości i wyciągania z kapelusza.

\(\displaystyle{ \sum_{k=0}^{n}k^2= \frac{1}{3}\left((n+1)^3-\frac{(n+1)(3n+2)}{2} \right)=\frac{n(n+1)(2n+1)}{6}}\)

PS. Sumowanie zacząłem od \(\displaystyle{ k=0}\) ze względów estetycznych i minimalnego uproszczenie rachunków jednym miejscu nie ma jednak takiej konieczności i można zacząć od \(\displaystyle{ k=1}\). Co da standardowy wzór

\(\displaystyle{ \sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}}\)

PS. PS. Takie samo rozumowanie można powtarzać dla wyższych potęg. Istotne jest by przy obliczaniu \(\displaystyle{ \sum_{}^{} k^{s}}\) znać wszystkie poprzednie jawne wzory na \(\displaystyle{ \sum_{}^{} k^{s-1}, \ \ \sum_{}^{} k^{s-2}, \ \ ... , \sum_{}^{} k^{0}}\). Tak jak tu posłużyłem się milcząco znajomością \(\displaystyle{ \sum_{}^{} k}\) oraz \(\displaystyle{ \sum_{}^{} 1}\) choć to uznaje już za ogólnie znane.

Awatar użytkownika
mariuszm
Użytkownik
Użytkownik
Posty: 6743
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Pomógł: 1221 razy

Re: Suma kwadratów liczb naturalnych

Post autor: mariuszm » 5 kwie 2018, o 21:29

Jest kilka sposobów

1. Interpolacja wielomianowa (Lagrange , Newtona)
2. Rekurencja i funkcje tworzące
3. Rachunek różnicowy


http://wazniak.mimuw.edu.pl/index.php?t ... etna_1/Wykład_4:_Sumy_skończone_i_rachunek_różnicowy

\(\displaystyle{ \begin{cases} s_{0}=0 \\ s_{n}=s_{n-1}+n^2 \end{cases}\\ S\left( x\right)= \sum_{n=0}^{ \infty }{s_{n}x^{n}}\\ \sum_{n=1}^{ \infty }s_{n}x^{n}=\sum_{n=1}^{ \infty }{s_{n-1}x^{n}}+\sum_{n=1}^{ \infty }{n^2x^{n}}\\ \sum_{n=0}^{ \infty }s_{n}x^{n}=x\sum_{n=1}^{ \infty }{s_{n-1}x^{n-1}}+\sum_{n=0}^{ \infty }{n^2x^{n}} \\ \sum_{n=0}^{ \infty }s_{n}x^{n}=x\sum_{n=0}^{ \infty }{s_{n}x^{n}}+\sum_{n=0}^{ \infty }{n^2x^{n}} \\}\)
\(\displaystyle{ \sum_{n=0}^{ \infty }x^{n}= \frac{1}{1-x} \\ \frac{ \mbox{d}}{ \mbox{d}x }\left(\sum_{n=0}^{ \infty }x^{n} \right) = \frac{ \mbox{d}}{ \mbox{d}x }\left( \frac{1}{1-x} \right) \\ \sum_{n=0}^{ \infty }nx^{n-1}=-\frac{1}{\left( 1-x\right)^{2} } \cdot \left( -1\right) \\ \sum_{n=0}^{ \infty }nx^{n-1}= \frac{1}{\left( 1-x\right)^{2}} \\ \sum_{n=0}^{ \infty }nx^{n}=\frac{x}{\left( 1-x\right)^{2}}\\ \frac{ \mbox{d}}{ \mbox{d}x }\left(\sum_{n=0}^{ \infty }nx^{n} \right) = \frac{ \mbox{d}}{ \mbox{d}x }\left(\frac{x}{\left( 1-x\right)^{2}} \right) \\ \sum_{n=0}^{ \infty }{n \cdot nx^{n-1}}=\frac{1}{\left( 1-x\right)^2 }+\frac{\left( -2\right) }{\left( 1-x\right)^{3} } \left( -1\right) \\ \sum_{n=0}^{ \infty }n^2x^{n-1}=\frac{1}{\left( 1-x\right)^2 }+\frac{2x}{\left( 1-x\right)^2 }\\ \sum_{n=0}^{ \infty }n^2x^{n}=\frac{x}{\left( 1-x\right)^2 }+\frac{2x^2}{\left( 1-x\right)^3 }\\}\)

\(\displaystyle{ \frac{ \mbox{d}}{ \mbox{d}x } \left(\sum_{n=0}^{ \infty }n^2x^{n} \right)= \frac{ \mbox{d}}{ \mbox{d}x }\left(\frac{x}{\left( 1-x\right)^2 }+\frac{2x^2}{\left( 1-x\right)^3 } \right) \\ \sum_{n=0}^{ \infty }n^2 \cdot nx^{n-1}=\frac{1}{\left( 1-x\right)^2 }+x \cdot \frac{\left( -2\right) }{\left( 1-x\right)^3 }\left( -1\right) +\frac{4x}{\left( 1-x\right)^3 }+2x^2 \cdot \frac{\left( -3\right) }{\left( 1-x\right)^4 }\left( -1\right) \\ \sum_{n=0}^{ \infty }n^3x^{n-1}=\frac{1}{\left( 1-x\right)^2 }+\frac{6x}{\left( 1-x\right)^3 }+\frac{6x^2}{\left( 1-x\right)^4 }\\ \sum_{n=0}^{ \infty }n^3x^{n}=\frac{x}{\left( 1-x\right)^2 }+\frac{6x^2}{\left( 1-x\right)^3 }+\frac{6x^3}{\left( 1-x\right)^4 }\\}\)

\(\displaystyle{ \left( 1-x\right)S\left( x\right)=\frac{x}{\left( 1-x\right)^2 }+\frac{2x^2}{\left( 1-x\right)^3 }\\ S\left( x\right)=\frac{x}{\left( 1-x\right)^3 }+\frac{2x^2}{\left( 1-x\right)^4 }\\}\)

Chociaż może wygodniej byłoby przedstawić ten wielomian w postaci ilorazu funkcji \(\displaystyle{ \Gamma}\)
Ostatnio zmieniony 5 kwie 2018, o 23:05 przez mariuszm, łącznie zmieniany 1 raz.

Awatar użytkownika
Rafsaf
Użytkownik
Użytkownik
Posty: 466
Rejestracja: 19 lut 2017, o 11:04
Płeć: Mężczyzna
Lokalizacja: Podkarpacie/Wrocław
Podziękował: 54 razy
Pomógł: 80 razy

Re: Suma kwadratów liczb naturalnych

Post autor: Rafsaf » 5 kwie 2018, o 22:00

Z kompendium, gorąco polecam, do prostszych przykładów wystarczy.

258562.htm

a4karo
Użytkownik
Użytkownik
Posty: 18544
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 6 razy
Pomógł: 3141 razy

Re: Suma kwadratów liczb naturalnych

Post autor: a4karo » 5 kwie 2018, o 22:13

\(\displaystyle{ \begin{tikzpicture} \node at (0,5) {$1$}; \node at (5,5) {$\to 1^2$}; \node at (0,4.5) {$1\ 2\ 1$}; \node at (5,4.5) {$\to 2^2$}; \node at (0,4) {$1\ 2\ 3\ 2\ 1$}; \node at (5,4) {$\to 3^2$}; \node at (0,3.5) {$1\ 2\ 3\ 4\ 3\ 2\ 1$}; \node at (5,3.5) {$\to 4^2$}; \node at (0,3) {$1\ 2\ 3\ 4\ 5\ 4\ 3\ 2\ 1$}; \node at (5,3) {$\to 5^2$}; \node at (0,2) {$1\ 2\ 3\ 4\ 5\ \ \ \ \ \ 5\ 4\ 3\ 2\ 1$}; \node at (0,1.5) {$2\ 3\ 4\ 5\ \ \ \ \ \ \ \ \ \ \ 5\ 4\ 3\ 2$}; \node at (0,1) {$3\ 4\ 5\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 5\ 4\ 3$}; \node at (0,0.5) {$4\ 5\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 5\ 4$}; \node at (0,0) {$5\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 5$}; \end{tikzpicture}}\)
Ten szkic dowodu znalazłem w Księdze liczb, Conwaya i Guy'a

Pięć pierwszych wierszy sumuje się do \(\displaystyle{ 1^2+\dots+5^2}\)
Dolne trójkąty też sie sumują do \(\displaystyle{ 1^2+\dots+5^2}\) (dodajemy po przekątnych).


Zatem suma liczb we wszystkich trójkątach wynosi \(\displaystyle{ 3(1^2+\dots+5^2)}\).

A z drugiej strony jest równa \(\displaystyle{ (1+2+3+4+5)\cdot 11}\).

Stąd \(\displaystyle{ 1^2+\dots+5^2=\frac{(1+2+3+4+5)\cdot 11}{3}}\)
Łatwo sobie wyobrazić co się stanie, gdy \(\displaystyle{ 5}\) zastąpimy dowolną liczbą naturalną \(\displaystyle{ n}\). Otrzymamy
\(\displaystyle{ 1^2+2^2+\dots+n^2=\frac{(1+2+\dots+n)(2n+1)}{3}}\)
Ostatnio zmieniony 5 kwie 2018, o 22:37 przez a4karo, łącznie zmieniany 1 raz.

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15009
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 145 razy
Pomógł: 4974 razy

Re: Suma kwadratów liczb naturalnych

Post autor: Premislav » 5 kwie 2018, o 22:16

mariuszm, jaki sposób chcesz to zrealizować z wykorzystaniem funkcji tworzących? Akurat tutaj jak dla mnie średnio pasują, ale może czegoś nie widzę.

Można również wykorzystać zadziwiającą tożsamość
\(\displaystyle{ \sum_{k=1}^{n}k^2 + \sum_{k=1}^{n} \sum_{i=1}^{k}i = (n+1) \sum_{k=1}^{n}k}\)
(kiedyś user mdd pisał o czymś ogólniejszym w tym kształcie).
Istnieje dowód geometryczny tej zależności, ale nie śmigam w TikZ. Tak ideowo: robimy taką figurę z ustawionych obok siebie krótszym bokiem (takie schodki) prostokątów, poczynając od \(\displaystyle{ (n+1)\times 1}\), a kończąc na \(\displaystyle{ (n+1)\times n}\). Z prostokącika \(\displaystyle{ (n+1)\times k}\), gdzie \(\displaystyle{ k \in\left\{ 1\ldots n\right\}}\) odcinamy kwadrat \(\displaystyle{ k\times k}\).
Potem patrzymy na prostokąty które wystają nad te kwadraty…

Po przekształceniu:
\(\displaystyle{ {\red \sum_{k=1}^{n}k^2 } = (n+1) \sum_{k=1}^{n}k- \sum_{k=1}^{n} \sum_{i=1}^{k}=\\= \frac{n(n+1)^2}{2}- \sum_{k=1}^{n} \frac{k(k+1)}{2}=\\=\frac{n(n+1)^2}{2}-{\red \frac 1 2 \sum_{k=1}^{n}k^2}- \frac 1 2\sum_{k=1}^{n}k}\),
czyli
\(\displaystyle{ \frac 3 2 \sum_{k=1}^{n} k^2= \frac{n(n+1)^2}{2}- \frac{n(n+1)}{4}= \frac{n(n+1)(2n+1)}{4}}\)
oraz wreszcie
\(\displaystyle{ \sum_{k=1}^{n} k^2= \frac{n(n+1)^2}{2}- \frac{n(n+1)}{4}= \frac{n(n+1)(2n+1)}{6}}\)

Awatar użytkownika
mdd
Użytkownik
Użytkownik
Posty: 1873
Rejestracja: 14 kwie 2013, o 10:58
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 506 razy

Suma kwadratów liczb naturalnych

Post autor: mdd » 5 kwie 2018, o 22:47

Premislav pisze:Można również wykorzystać zadziwiającą tożsamość
\(\displaystyle{ \sum_{k=1}^{n}k^2 + \sum_{k=1}^{n} \sum_{i=1}^{k}i = (n+1) \sum_{k=1}^{n}k}\)
(kiedyś user mdd pisał o czymś ogólniejszym w tym kształcie).
Kiedyś przyśniło mi się coś takiego: https://www.matematyka.pl/352928.htm#p5179034

Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 2942
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 72 razy
Pomógł: 977 razy

Re: Suma kwadratów liczb naturalnych

Post autor: Janusz Tracz » 5 kwie 2018, o 23:03

mariuszm, "Interpolacja wielomianowa (Lagrange , Newtona)" Ta metoda chyba będzie wymagała na końcu dowodu indukcyjnego potwierdzającego przypuszczenie. O ile mówimy o tym samym. Ja rozumiem to tak że zakładamy istnienie takich \(\displaystyle{ a,b,c,d}\) że dla każdego \(\displaystyle{ n\in\NN}\) \(\displaystyle{ 1^2+2^2+3^2+...+n^2=an^3+bn^2+cn+d}\). Po wstawianiu pierwszych czterech "sum" dostaniemy układ równań liniowych którego rozwiązaniem będą \(\displaystyle{ a,b,c,d}\) ale to że wzór będzie działał dla pieszych czterech liczb nie gwarantuje działania dla dowolnego \(\displaystyle{ n}\). Przypuszczenie potwierdzamy indukcyjnie.

Rafsaf metoda zaburzania sumy to sformalizowanie sposobu jaki pokazałem na początku z \(\displaystyle{ (k+1)^3-k^3=3k^2+3k+1}\) idea jest ta sama.

Premislav ten wzór kojarzy mi się z przekształceniem Abela dzięki niemu też można udowodnić tezę zadania.

\(\displaystyle{ \sum_{j=m+1}^{m+k}a_jb_j= \sum_{l=m+1}^{m+k} \left( \sum_{i=1}^{l}a_i(b_l-b_{l+1}) \right)-b_{m+1} \sum_{i=1}^{m}a_i+ b_{m+k+1}\sum_{i=1}^{m+k}a_i}\)

jak położymy \(\displaystyle{ a_i=b_i=i}\) oraz \(\displaystyle{ m=0}\) to skończymy z tym co Premislav zaproponował. Ten sposób liczenia sumy jest też związany z liczeniem sumy przez części
Ostatnio zmieniony 5 kwie 2018, o 23:16 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości: kojarzy.

Awatar użytkownika
mariuszm
Użytkownik
Użytkownik
Posty: 6743
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Pomógł: 1221 razy

Re: Suma kwadratów liczb naturalnych

Post autor: mariuszm » 5 kwie 2018, o 23:18

Premislav pisze:mariuszm, jaki sposób chcesz to zrealizować z wykorzystaniem funkcji tworzących? Akurat tutaj jak dla mnie średnio pasują, ale może czegoś nie widzę.
A jednak można, dopisałem rozwiązanie rekurencji z wykorzystaniem funkcji tworzących
we wpisie z 5 kwietnia 2018, 21:29
Tylko że wygodniej byłoby zapisać wielomian jako sumę górnych silni
bądź jak kto woli sumę ilorazów funkcji \(\displaystyle{ \Gamma}\)

Janusz Tracz, chyba masz racje z tą indukcją
Korzystając z wzorów interpolacyjnych Lagrange bądź Newtona nie będziemy musieli
używać współczynników nieoznaczonych i rozwiązywać układu równań liniowych

Poszukajcie o liczbach i wielomianach Bernoulliego


Jeśli chodzi o funkcję tworzącą to


\(\displaystyle{ f\left( t,x\right)=\frac{te^{tx}}{e^{t}-1}= \sum_{n=0}^{ \infty }B_{n}\left( x\right)\frac{t^n}{n!}}\)

Elayne
Użytkownik
Użytkownik
Posty: 802
Rejestracja: 24 paź 2011, o 01:24
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 61 razy
Pomógł: 248 razy

Suma kwadratów liczb naturalnych

Post autor: Elayne » 22 kwie 2018, o 08:56


Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3981
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 94 razy
Pomógł: 387 razy

Re: Suma kwadratów liczb naturalnych

Post autor: arek1357 » 22 kwie 2018, o 20:39

Wielkie brawa fszystkim....

ODPOWIEDZ