Фомула за сбора от квадратите до n-то число

[Гост]

Формулата ми я дадоха преди време (мисля, че бях 8 клас) , но трябваше просто да я помним и наскоро ми се падна на състезание (трябваше ми за задача) , но не я помнех.Пускам я за 12 клас защото идея нямам за доказателството, а и съм 12 клас ;D. Формулата е 1^2 + 2^2 + 3^2 ....... + n^2 = n.(n+1)(2n+1)/6. n принадлежи на N, разбира се :D.
Мога да я докажа , проблемът е извеждането.

[ptj]

Варианта е да я помниш.

Mоже да я изведеш например с интерполационен полином на Лагранж, като знаеш че е полином от 3-та степен и затова ще са ти необходими 4 точки и съответните функционални стойности. Примерно [tex]x=1,2,3,4[/tex] и [tex]f(1),f(2),f(3),f(4)[/tex].

Проблема е, че това ще ти отнеме време...

П.П. Възможно е да има и други по-бързи начини за извеждане.

[Гост]

Проблемът е, че нямам идея какви са тези интерполационни полноми. Не знам къде съм бил като сме ги учили :(

[Knowledge Greedy]

[tex]f(n)=1^2+2^2+3^2+... +n^2[/tex]

"Бързо" извеждане на тази сума може да стане от по-високата сума - от третите степени (Не е необходимо да се знае и тази сума, макар че тя се помни още по-лесно!).
[tex]S(n)=1^3+2^3+3^3+... +n^3[/tex]

[tex]S(n+1)=1^3+2^3+3^3+... +n^3+(n+1)^3[/tex]

Да образуваме разликата [tex]\Delta = S(n+1)-S(n)[/tex]
От една страна тя е [tex](n+1)^3[/tex]

От друга страна е [tex]\Delta=S(n+1)-S(n)=1^3+(1+1)^3-1^3+(2+1)^3-2^3+(3+1)^3-3^3+...+(n+1)^3-n^3[/tex]

Извършваме [tex]n[/tex] пъти опростяването [tex](k+1)^3-k^3=3k^2+3k+1[/tex] - за [tex]k=1; \,\ k=2, \,\ k=3, \,\ ...[/tex] и накрая за [tex]k=n[/tex]

Групираме вторите степени като изнесем общ множител [tex]3[/tex] и отделно групираме първите степени - също изнасяйки общ множител [tex]3[/tex]

[tex]\Delta=1+3f(n)+3(1+2+3+...+n)+n.1[/tex]
Считаме, че сумата [tex]1+2+3+...+n=\frac{n(n+1)}{2}[/tex] e лесно постижима и затова като приравним двете изразявания
[tex]1+3f(n)+3\frac{n(n+1)}{2}+n.1=(n+1)^3[/tex]

получаваме [tex]3f(n)=(n+1)^3-3\frac{n(n+1)}{2}-n-1[/tex], от което след кратко опростяване извеждаме

[tex]f(n)=\frac{1}{6}n(n+1)(2n+1)[/tex]

Идеята на ptj с Лагранж много ми хареса, принципна е и кристално ясна, но... сега едва ли другаде освен в НПМГ я учат и второ - техниката на смятане трябва да е на твърде високо ниво. А ако това е така, то човекът ще си знае и формулата

[0xdeadbeef]

Гледай картинката

Първо записваме всяко число [tex]n^2[/tex] като сума от [tex]n[/tex] от [tex]n[/tex], сега нанасяме сумите в "триъгълник", после правим две копия на триъгълника като го ротираме на [tex]120^o[/tex] и [tex]240^o[/tex], накрая събираме сумите по нива.
Имаме
[tex](2n+1)(1+2+3+\dots+n) = 3(1^2 + 2^2 +\dots +n^2)[/tex]

[Гост]

Едва ли не ми казваш, че съм идиот ? Най-вероятно решението на ptj ще е по -красиво, но пък твоето на мен ми е ясно. Надявам се в СУ да настигна великите НПМГ .

[0xdeadbeef]

казвам ти лесен начин да си пропомниш формулата, ако я забравиш

[Гост]

Говорех на Greedy.Понякога съжалявам като попитам нещо.Изкарват ме идиот. Иначе мерси за решението.Този метод с триъгълниците сега ще го пробвам за третите степени да видим дали ще стане.

[ptj]

Идеята на полинома на Лагранж е изключително конструктивна. Той представлява сума от полиноми от n-та степен за (n+1) точки и техните функционални стойности. Същността и е :
[tex]i[/tex]- тото събираемо да приема стойност нула за всички точки, различни от [tex]x_i[/tex],
а в точката [tex]x_i[/tex] да приема съответната функционална стойност [tex]f(x_i)[/tex].


[tex]L_n(x)=\sum\limits^{n}_{i=1}\bigg(_{j\ne j;}\prod_{j=1}^n \frac{x-x_j}{x_i-x_j}\bigg)f(x_i)[/tex]

Например за 4 точки полинома на Лагрaнж ще изглежда по следния начин:

[tex]L_4(x)=\frac{(x-x_2)(x-x_3)(x-x_4)}{(x_1-x_2)(x_1-x_3)(x_1-x_4)}f(x_1)+\frac{(x-x_1)(x-x_3)(x-x_4)}{(x_2-x_1)(x_2-x_3)(x_2-x_4)}f(x_2)+[/tex]

[tex]\frac{(x-x_1)(x-x_2)(x-x_4)}{(x_3-x_1)(x_3-x_2)(x_3-x_4)}f(x_3)+\frac{(x-x_1)(x-x_2)(x-x_3)}{(x_4-x_1)(x_4-x_2)(x_4-x_3)}f(x_4)[/tex]

В горния пример [tex]f(x)=f(n)=\sum_{i=1}^n i^2[/tex] . ([tex]x[/tex] приема само естесвени стойности)

[tex]x_1=1; x_2=2; x_3=3; x_4=4[/tex] и [tex]f(1)=1; f(2)=5; f(3)=14; f(4)=30[/tex] ,

т.е. ще получим

[tex]\frac{(x-2)(x-3)(x-4)}{(1-2)(1-3)(1-4)}f(1)+\frac{(x-1)(x-3)(x-4)}{(2-1)(2-3)(2-4)}f(2)+[/tex]

[tex]+\frac{(x-1)(x-2)(x-4)}{(3-1)(3-2)(3-4)}f(3)+\frac{(x-1)(x-2)(x-3)}{(4-1)(4-2)(4-3)}f(4)=[/tex]

[tex]\frac{(x-2)(x-3)(x-4)}{(1-2)(1-3)(1-4)}.1+\frac{(x-1)(x-3)(x-4)}{(2-1)(2-3)(2-4)}.5+[/tex]

[tex]+\frac{(x-1)(x-2)(x-4)}{(3-1)(3-2)(3-4)}.14+\frac{(x-1)(x-2)(x-3)}{(4-1)(4-2)(4-3)}.30=[/tex]

[tex]\frac{(x-2)(x-3)(x-4)}{(-1)(-2)(-3)}.1+\frac{(x-1)(x-3)(x-4)}{1(-1)(-2)}.5+[/tex]

[tex]+\frac{(x-1)(x-2)(x-4)}{(2)(1)(-1)}.14+\frac{(x-1)(x-2)(x-3)}{(3)(2)(1)}.30=[/tex]

...

[tex]=\frac{x^3}{3}+\frac{x^2}{2}+\frac{x}{6}=\frac{x}{6}(2x^2+3x+1)=\frac{x(x+1)(2x+1)}{6}[/tex]

Понеже (n+1) точки определят еднозначно полином от [tex]n[/tex]-та степен, то

[tex]f(n)=\frac{n(n+1)(2n+1)}{6}[/tex] .

П.П. Принципа е универсален, но сметките не са особено приятни.

[0xdeadbeef]

Ами няма да стане с триъгълници за кубовете. По скоро с триизмерния им вариант.

[Гост]

ptj, не казвам, че си сбъркал.По това, което разбрах j=0 и i=0.Защо да са =1

[0xdeadbeef]

а, с квадрати можело ...

[ptj]

Има и друг универсален начин - с неопределени коефициенти.

т.е. [tex]f(n)=a.n^3+b.n^2+c.n+d[/tex]

Даваш 4 стойности на [tex]n[/tex] и получаваш система за [tex]a,b,c,d[/tex].

[Гост]

Интересен ми беше полинома на Лагранж.Все си мисля, че трябва i=j=0. А ти казваш =1 ?

[Knowledge Greedy]

Едва ли не ми казваш, че съм идиот ? Най-вероятно решението на ptj ще е по -красиво, но пък твоето на мен ми е ясно. Надявам се в СУ да настигна великите НПМГ .

Уважаеми Гост! В никакъв случай не бих си позволил подобни квалификации. Ние се учим взаимно, като разликите между нас са нищожни - от няколко години, до няколко десетки години; от повече или по-малко рутина и житейски опит; количество на дипломите и т.н.

Ето аз се опитвах да направя полинома на ptj, но все не докарвах коефициентите му и се отказах, като видях, че ме е изпреварил. Що се отнася до учебните програми, амбициите на отделните преподаватели и техните възпитаници - наистина в математическите гимназии (вкл. ПМГ и НПМГ) имат по-големи възможности. Другаде просто няма време и оставяме материал за работа на колегите от по-високите нива.

Що се отнася до красотата на решението, аз харесах идеята. Тя създава усещането за успех. По-скоро безпощадност, сигурност, че задачата ще бъде победена. В крайна сметка и ptj си признава, че сметките са отвратителни. Такова решение е далече от представите ни за красота. По-скоро в опитите на 0xdeadbeef и геометричните интерпретации може да потърсим някаква красота. Но и всеки си има различна представа за красотата...

[ptj]

ptj, не казвам, че си сбъркал.По това, което разбрах j=0 и i=0.Защо да са =1

[tex]i[/tex]-тото събираемо е :

[tex]\bigg(_{j\ne j;}\prod_{j=1}^n \frac{x-x_j}{x_i-x_j}\bigg)f(x_i)[/tex] ,

докато [tex]i,j[/tex] са просто индекси.

[pipi langstrump]

Възможно най-лесния и прост начин, който действа за всякакви степени:

Скрит текст: покажи

http://www.trans4mind.com/personal_development/mathematics/series/sumNaturalSquares.htm#summation

[drago]

... Тя създава усещането за успех. По-скоро безпощадност, сигурност, че задачата ще бъде победена. В крайна сметка и ptj си признава, че сметките са отвратителни. ...

На мен не ми създава такова усещане, да си призная. По-скоро си мисля, че точно твоята идея е "истината" за тази задача, за произволна степен, но в малко обърнат вариант.
...Да не говорим, че априори ние не можем да сме сигурни, че сумата от k-тите степени на последователните числа от 1 до n е полином от n+1 - ва степен, че да го търсим с интерполация. Това може да се разгледа като самостоятелна задача, ето например един линк: viewtopic.php?f=10&t=13569
Освен това с интерполация или с метод на неопределени коефициенти не можеш да намериш рекурентната връзка м/у формулите за последователни k.
След всички тези бла-бла, нека означим [tex]P_k(n)=1^k+2^k+\dots n^k[/tex]. Имаме:
[tex]P_k(n+1)-P_k(n)=(n+1)^k[/tex].
Сега малко отклонение. За произволен полином [tex]P(x)[/tex], нека означим [tex]\Delta P(x)=P(x+1)-P(x)[/tex]. Нарича се крайна разлика (от първи ред със стъпка 1) има много приложения в числените методи, теория на апроксимациите и т.н.
Едно от лесните и свойства е, че [tex]\Delta P(x)[/tex] е полином с поне една степен по-ниска от [tex]P(x)[/tex]. Тук възниква обратната задача: ако знаем колко е [tex]\Delta P(x)[/tex] (някакъв полином), можем ли да възстановим [tex]P(x)[/tex] и обезателно ли той ще бъде полином. Отговорът е ДА, можем да го възстановим. (с точност до константа, тъй като прибавяйки константа към [tex]P[/tex] това не променя [tex]\Delta P[/tex]). Да допуснем, че сме намерили [tex]Q_1, Q_2,\dots, Q_{k-1}[/tex] така че:
[tex]\Delta Q_j(x)=x^j\,,\, j=0,1,\dots, k-1[/tex]
Имаме [tex]\Delta Q_{k-1}(x)= x^{k-1}[/tex]. Нека [tex]Q(x)=\int P_{k-1}(x)[/tex]. Тогава:
[tex]\Delta Q(x)=x^{k}/k[/tex] или [tex]\Delta (kQ(x))=x^{k}[/tex]. T.e. намерихме [tex]Q_k(x) := kQ(x)[/tex], такъв че [tex]\Delta Q_k(x)=x^k[/tex].

Да се върнем към нашия случай. [tex]P_k[/tex] се определя еднознчано от условията:
[tex]P_k(0)=0[/tex]
[tex]\Delta P_k(x)=(x+1)^k[/tex].
Използвайки, горните разсъждения и като развием [tex](x+1)^k[/tex], можем да намерим рекурентна формула за [tex]P_k[/tex].

П.П. @Гост (дето го правили на идиот). Не трябва да се чувстваш така, ако мъчиш нещо дълго време и после някой изведнъж те светне как да стане. На всеки постоянно се случва, а на който не се случва значи е спрял да се равива

[monika_at]

Варианта е да я помниш.

Mоже да я изведеш например с интерполационен полином на Лагранж, като знаеш че е полином от 3-та степен и затова ще са ти необходими 4 точки и съответните функционални стойности. Примерно [tex]x=1,2,3,4[/tex] и [tex]f(1),f(2),f(3),f(4)[/tex].

Проблема е, че това ще ти отнеме време...

П.П. Възможно е да има и други по-бързи начини за извеждане.

Сопри се, с тези интерполационни полиноми!

[ptj]

http://mathschallenge.net/library/number/sum_of_cubes

Това е универсалната идея.

[pipi langstrump]

http://mathschallenge.net/library/number/sum_of_cubes

Това е универсалната идея.

Ами нали за същото дадох линк малко по-нагоре

[ptj]

Извинения Пипи, не съм обърнал внимание на линка ти.