Suma potęg

Ze względu na specyfikę metody - osobny dział.
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Suma potęg

Post autor: Bran »

Dla \(\displaystyle{ n,r \in \NN, n \in \NN}\) oznaczmy przez \(\displaystyle{ S_r(n) = 1^r + 2^r + \ldots + n^r}\).
a) Sprawdź, że dla \(\displaystyle{ (n+1)^{r+1} - (n+1) = {r+1 \choose 1}S_r(n) + {r+1 \choose 2}S_{r-1}(n) + \ldots + {r+1 \choose r}S_1(n).}\)
b) Wyprowadź wzory na \(\displaystyle{ S_1(n), \; S_2(n),\; S_3(n), \; S_4(n)}\). Udowodnij ich prawdziwość stosując zasadę indukcji matematycznej.

b)
\(\displaystyle{ S_1(n) = 1 + 2 + \ldots + n = \frac{n^2+n}{2}\\
S_2(n) = 1^2 + 2^2 + \ldots + n^2 = \frac{n^3+n}{2} \\
S_3(n) = 1^3 + 2^3 + \ldots + n^3 = \frac{n^4+n}{2}\\
S_4(n) = 1^4 + 2^4 + \ldots + n^4 = \frac{n^5+n}{2} }\)


Zatem \(\displaystyle{ S_r(n) = \frac{n^{r+1}+n}{2}}\)


Znowu mam ten sam problem - indukcja na dwóch zmiennych, jakieś to dla mnie nieintuicyjne. Mógłbym prosić o jakąś podpowiedź?
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Suma potęg

Post autor: Janusz Tracz »

Bran pisze: 19 kwie 2020, o 23:51 \(\displaystyle{ S_1(n) = 1 + 2 + \ldots + n = \frac{n^2+n}{2}\\
S_2(n) = 1^2 + 2^2 + \ldots + n^2 = \frac{n^3+n}{2} \\
S_3(n) = 1^3 + 2^3 + \ldots + n^3 = \frac{n^4+n}{2}\\
S_4(n) = 1^4 + 2^4 + \ldots + n^4 = \frac{n^5+n}{2} }\)


Zatem \(\displaystyle{ S_r(n) = \frac{n^{r+1}+n}{2}}\)
Skąd ten wniosek? \(\displaystyle{ S_2(3)}\) już się nie zgada. Ogólnie to jawny wzór na \(\displaystyle{ S_r(n)}\) jest dość skomplikowany więc nie tędy droga.

Dodano po 10 godzinach 38 minutach 26 sekundach:
Warto się zastanowić jak się oblicza sumy kolejnych potęg (dla mniejszych \(\displaystyle{ r}\)) powiedzmy, że chcesz obliczyć \(\displaystyle{ \red{S_2(n)}}\) (milcząco zakładając, że znamy \(\displaystyle{ \blue{S_1(n)}}\) oraz \(\displaystyle{ \blue{S_0(n)}}\)) zauważ, że można to uczynić w taki sposób, zauważmy niezależnie, że dla naturalnych \(\displaystyle{ k}\) dwumian pozwala napisać:

\(\displaystyle{ (k+1)^3-k^3= \sum_{j=0}^{2} {3 \choose j}k^j }\)

równość ta jest prawdziwa dla dowolnego naturalnego \(\displaystyle{ k}\) zatem można zsumować ją stronami po \(\displaystyle{ k=1,2,...,n}\)

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

sumę po lewej można łatwo policzyć bo się teleskopuje a po prawej zamieniamy kolejność sumowania.

\(\displaystyle{ (n+1)^3-1= \sum_{j=0}^{2}\sum_{k=1}^{n} {3 \choose j}k^j }\)

jako, że \(\displaystyle{ {3 \choose j}}\) jest niezależne od \(\displaystyle{ k}\) można napisać:

\(\displaystyle{ (n+1)^3-1= \sum_{j=0}^{2} {3 \choose j}\blue{\sum_{k=1}^{n}k^j } }\)

rozwińmy zewnętrzną sumę:

\(\displaystyle{ (n+1)^3-1= \sum_{j=0}^{2} {3 \choose j}\blue{\sum_{k=1}^{n}k^j } = {3 \choose 0}\blue{\sum_{k=1}^{n}k^0 }+{3 \choose 1}\blue{\sum_{k=1}^{n}k^1 }+{3 \choose 2}\red{\sum_{k=1}^{n}k^2 } }\)

Zapiszmy teraz te sumy w kontekście \(\displaystyle{ S_r(n)}\) czyli

\(\displaystyle{ (n+1)^3-1={3 \choose 0}\blue{S_0(n)}+{3 \choose 1}\blue{S_1(n)}+{3 \choose 2}\red{S_2(n)} }\)

Aby maksymalnie upodobnić to do wzoru z podpunktu \(\displaystyle{ a}\) zauważmy, że \(\displaystyle{ \blue{S_0(n)}}\) to suma \(\displaystyle{ n}\) jedynek zatem jest równa \(\displaystyle{ n}\) co pozwoli napisać:

\(\displaystyle{ (n+1)^3-(n+1)={3 \choose 1}\blue{S_1(n)}+{3 \choose 2}\red{S_2(n)} }\)

To pokazuje skąd bierze się wzór z pierwszego podpunktu. Jeśli teraz uogólnisz to rozumowanie dla dowolnego \(\displaystyle{ r}\) to dostaniesz wzór z podpunktu \(\displaystyle{ a}\). Natomiast aby sprawnie wyznaczać \(\displaystyle{ S_r(n)}\) co przyda się w podpunkcie \(\displaystyle{ b}\) zauważmy, że można go przekształcić:
w kontekście tego co wyżej:    
oraz ogólnej

\(\displaystyle{ (n+1)^{r+1} - (n+1) = {r+1 \choose 1}\red{S_r(n)} + {r+1 \choose 2}\blue{S_{r-1}(n)} + \ldots + {r+1 \choose r}\blue{S_1(n)}}\)

\(\displaystyle{ (n+1)^{r+1} - (n+1) = {r+1 \choose r}\red{S_r(n)} + {r+1 \choose r-1}\blue{S_{r-1}(n)} + \ldots + {r+1 \choose 1}\blue{S_1(n)}}\)

\(\displaystyle{ (n+1)^{r+1} - (n+1) = {r+1 \choose r}\red{S_r(n)} + \sum_{j=1}^{r-1} {r+1 \choose j} \blue{S_j(n)} }\)

\(\displaystyle{ (n+1)^{r+1} - (n+1) - \sum_{j=1}^{r-1} {r+1 \choose j} \blue{S_j(n)} = (r+1)\red{S_r(n)} }\)

\(\displaystyle{ \red{S_r(n)} = \frac{(n+1)^{r+1} - (n+1) - \sum_{j=1}^{r-1} {r+1 \choose j} \blue{S_j(n)}}{r+1} }\)

PS indukcją udowadniamy pierwszą równość czyli tak naprawdę wzór dwumianowy przy ustalonym \(\displaystyle{ r}\) indukcją po \(\displaystyle{ k}\).

Dodano po 5 minutach 59 sekundach:
W niektórych miejscach korzystam z wzoru \(\displaystyle{ {n \choose k} = {n \choose n-k} }\) jeśli byś się gdzieś zgubił w przekształceniach.
Ostatnio zmieniony 20 kwie 2020, o 11:26 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości: naprawdę.
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: Suma potęg

Post autor: Bran »

\(\displaystyle{ (n+1)^{r+1} - (n+1) = {r+1 \choose 1}S_r(n) + {r+1 \choose 2}S_{r-1}(n) + \ldots + {r+1 \choose r}S_1(n)}\)

Dowód indukcyjny:
Ustalmy \(\displaystyle{ r \in \NN}\) i sprawdźmy zależność dla \(\displaystyle{ n = 0}\)

\(\displaystyle{ 1 - 1 = {r+1 \choose 1}S_r(0) + {r+1 \choose 2}S_{r-1}(0) + \ldots + {r+1 \choose r}S_1(0)}\)
\(\displaystyle{ 0 = {r+1 \choose 1}\cdot 0 + {r+1 \choose 2}\cdot 0 + \ldots + {r+1 \choose r}\cdot 0}\)
\(\displaystyle{ 0 = 0}\)
Równanie jest prawdziwe.

Założenie indukcyjne: Dla ustalonego \(\displaystyle{ r}\) ustalmy dowolne \(\displaystyle{ n}\), takie że \(\displaystyle{ (n+1)^{r+1} - (n+1) = {r+1 \choose 1}S_r(n) + {r+1 \choose 2}S_{r-1}(n) + \ldots + {r+1 \choose r}S_1(n)}\)

Sprawdźmy teraz czy z założenia indukcyjnego wynika \(\displaystyle{ (n+2)^{r+1} - (n+2) = {r+1 \choose 1}S_r(n+1) + {r+1 \choose 2}S_{r-1}(n+1) + \ldots + {r+1 \choose r}S_1(n+1)}\)

Zacznijmy od lewej strony:
\(\displaystyle{ (n+2)^{r+1} - (n+2) = ((n+1)+1)^{r+1} - (n+1) - 1 = \\ = {r+1 \choose 0}(n+1)^{r+1} + {r+1 \choose 1}(n+1)^r + {r+1 \choose 2}(n+1)^{r-1} + \ldots + {r+1 \choose r}(n+1) + 1 - (n+1) -1 = \\ = (n+1)^{r+1} - (n+1) + {r+1 \choose 1}(n+1)^r + {r+1 \choose 2}(n+1)^{r-1} + \ldots + {r+1 \choose r}(n+1) = \\= {r+1 \choose 1}S_r(n) + {r+1 \choose 2}S_{r-1}(n) + \ldots + {r+1 \choose r}S_1(n) + {r+1 \choose 1}(n+1)^r + {r+1 \choose 2}(n+1)^{r-1} + \ldots + {r+1 \choose r}(n+1)}\)

Pierwsze przejście jest oczywiste, drugie przejście wynika z dwumianu Newtona, trzecie to proste przekształcenia, czwarte wynika z założenia indukcyjnego. Teraz, gdy się przyjrzymy ostatniej linijce do zauważymy, że wyrazy na czerwono są ostatnimi wyrazami poszczególnych sum, stad:
\(\displaystyle{ {r+1 \choose 1}S_r(n) + {r+1 \choose 2}S_{r-1}(n) + \ldots + {r+1 \choose r}S_1(n) + {r+1 \choose 1}(n+1)^r + {r+1 \choose 2}(n+1)^{r-1} + \ldots + {r+1 \choose r}(n+1) =\\= {r+1 \choose 1}S_r(n+1) + {r+1 \choose 2}S_{r-1}(n+1) + \ldots + {r+1 \choose r}S_1(n+1)}\)

a to kończy dowód.

Zastanawiam się o co chodziło autorowi w punkcie b)
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Suma potęg

Post autor: a4karo »

\(\displaystyle{ \red{{r+1 \choose 1}S_r(n) }+ {r+1 \choose 2}S_{r-1}(n) + \ldots + {r+1 \choose r}S_1(n) +\red{ {r+1 \choose 1}(n+1)^r }+ {r+1 \choose 2}(n+1)^{r-1} + \ldots + {r+1 \choose r}(n+1) =\\=\red{ {r+1 \choose 1}S_r(n+1)} + {r+1 \choose 2}S_{r-1}(n+1) + \ldots + {r+1 \choose r}S_1(n+1)}\)

Czyżbyś sugerował, że kolorowe składniki dają takie same sumy? Przecież taka równość nie zachodzi dla każdego wielomianu. Bez jego znanej postaci trudno uznać ten dowód za poprawny.
Poza tym taka równość dla wielomianów raczej nie zachodzi, bo `S_r(n+1)-S_r(n)` jest wielomianem stopnia niższego niż `r`, więc nie może być równy `(n+1)^r`
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: Suma potęg

Post autor: Bran »

Nie tylko sugeruję, ale twierdzę tak. Już tłumaczę:

\(\displaystyle{ {r+1 \choose 1} S_r(n) + {r+1 \choose 1} (n+1)^r}\)
teraz rozwijając pierwszy składnik sumy z definicji \(\displaystyle{ S_r(n)}\) otrzymujemy:

\(\displaystyle{ {r+1 \choose 1} \left( 1^r + 2^r + \ldots + n^r\right) + {r+1 \choose 1} (n+1)^r}\)
Po wyciągnięciu przed nawias symbolu Newtona mamy:
\(\displaystyle{ {r+1 \choose 1} \left( 1^r + 2^r + \ldots + n^r + (n+1)^r\right) }\)
Suma w nawiasie z definicji jest równa \(\displaystyle{ S_r(n+1)}\)

Zatem: \(\displaystyle{ {r+1 \choose 1} S_r(n) + {r+1 \choose 1} (n+1)^r = {r+1 \choose 1} S_r(n+1)}\)

Analogicznie z pozostałymi składnikami. Coś jak zwykle pomyliłem? :(
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Suma potęg

Post autor: a4karo »

Ok. `S_r` nie jest wielomianem st. `r`. Przepraszam
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Suma potęg

Post autor: Janusz Tracz »

Bran pisze: 21 kwie 2020, o 15:10 Zastanawiam się o co chodziło autorowi w punkcie b)
Mnie więcej o to o czym pisałem gdy wyprowadzałem wzór:

\(\displaystyle{ \red{S_r(n)} = \frac{(n+1)^{r+1} - (n+1) - \sum_{j=1}^{r-1} {r+1 \choose j} \blue{S_j(n)}}{r+1} }\)

Pokazałem w jaki sposób wyprowadzać wzory na \(\displaystyle{ \red{S_r(n)}}\) przy znanych \(\displaystyle{ \blue{S_1(n)},\blue{S_2(n)},...,\blue{S_{r-1}(n)}}\). Póki co pokazaliśmy indukcyjnie (nawet udało się to zrobić na dwa różne sposoby), że ta rekurencyjna zależność jest prawdziwa zatem będzie generować istotnie poprawne wzory na \(\displaystyle{ \red{S_r(n)}}\) przypuszczam, że autor chce abyś kilka z takich wzorów właśnie wyprodukował i dodatkowo dla ćwiczenia (bo to, że są prawdziwe to już wiemy) pokazał ich prawdziwość indukcyjnie. Czyli przykładowo

\(\displaystyle{ \red{S_2(n)}= \frac{(n+1)^3-(n+1)-{3 \choose 1}\blue{S_1(n)}}{ {3 \choose 2}}= \frac{n^3+3n^2+2n-3 \cdot \blue{ \frac{n^2+n}{2} }}{3} = \frac{2n^3+3n^2+n}{6} }\)

z tego wynika, że sumę kwadratów \(\displaystyle{ n}\) pierwszych liczb naturalnych można tak właśnie policzyć:

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

o prawdziwości tego wzoru zaświadcza prawdziwość rekurencji z której wynika niemniej jednak można go udowodnić indukcyjnie jako samodzielne twierdzono. Krok indukcyjny jest prosty i polega na zapisaniu:

\(\displaystyle{ \underbrace{1^2+2^2+3^2+...+n^2}_{\text{to wiemy czym jest z założenia }}+ (n+1)^2= \underbrace{\frac{2n^3+3n^2+n}{6}}_{\text{zatem to podstawiłem}} +(n+1)^2 }\)

wystarczy zatem pokazać, że \(\displaystyle{ \frac{2n^3+3n^2+n}{6} +(n+1)^2=\frac{2(n+1)^3+3(n+1)^2+(n+1)}{6}}\) sprowadza się to do rutynowych obliczeń na ułamkach (możesz wymnożyć stoami itd).
ODPOWIEDZ