Todistuksia 1+2+3+...+n = n(n+1)/2

Minusta selkein on laskea yhteen tuo sarja ja sama sarja käänteisessä järjestyksessä:

2 * summa =
(1 2 3 ... (n-2) (n-1) n)
(n (n-1) (n-2) ... 3 2 1)

järjestetään termit uudelleen

2 * summa = ((1 n) (2 (n-1)) (3 (n-2)) ... ((n-2) 3) ((n-1) 2) (n 1)
2 * summa = ((n 1) (n 1) (n 1) ... (n 1) (n 1) (n 1))
2 * summa = n * (n 1)
summa = n * (n 1) / 2

Järjestele summan termit uudelleen niin, että summaat ensin ensimmäisen ja viimeisen, sitten toisen ja toiseksi viimeisen, sitten kolmannen ka kolmanneksi viimeisen, jne. Jos n on pariton, jää jäljelle vielä keskimmäinen termi, joka on (n 1)/2
Näin jokainen noista pareista on täsmälleen n 1 (plus keskimmäinen termi, jos tarvitaan) ja niitä on n/2 kappaletta, eli summa on n/2 * (n 1).

Onnistuu myös helposti täydellisellä induktiolla.

Bijektiivinen todistus

Järjestetään 1 2 ... n täplää kolmioksi. Lisätään vielä yksi rivi, jossa on n 1 täplää. Nyt jokainen ylemmän kolmion täplä on yksi yhteen vastaavuudessa alimman rivin kahden alkion osajoukon kanssa seuraavan kuvion mukaisesti: https://www.desmos.com/calculator/w7yujv0qyu . Ja näitähän on (n 1)C2 = n(n 1)/2.

Keskimääräinen yhteenlaskettava on (n 1)/2, koska luvut asettuvat symmetrisesti lukusuoralla tämän suhteen. Koska yhteenlaskettavia on n kappaletta, saadaan 0.5(n^2 n).

Asian voi todeta kombinatoriikan kautta. Joukosta {1, 2, ..., n 1} voidaan muodostaa kahden alkion osajoukkoja (n 1)*n / 2, sillä ensimmäinen alkio voidaan valita n 1 tavalla ja toinen n tavalla, mutta koska alkioiden valintajärjestyksellä ei ole väliä, jokainen osajoukko tulee laskettua kahdesti, joten tulo jaetaan kahdella.

Toisaalta osajoukkojen määrä voidaan laskea myös seuraavasti: Osajoukkoja, joissa i on pienin luku on n 1 - i, sillä i:n lisäksi toiseksi alkioksi voidaan valita mikä tahansa alkio, joka on suurempi kuin i. Osajoukkojen määrä saadaan laskemalla yhteen tapaukset, joissa pienin luku i käy läpi kaikki mahdolliset tapaukset i = 1, 2, 3, ..., n. Siksi osajoukkojen määräksi tulee 1 2 ... n.

Koska osajoukkojen määrä ei voi riippua laskentatavasta, saadaan 1 2 ... n = n(n 1)/2

Kaava seuraa pinta-alalaskusta. Kun muodostetaan summaa 1 2 ... n vastaava kolmiomainen rakennelma yksikköneliöistä, tämän kuvion pinta-ala vastaa summaa. Tasokuvio koostuu suorakulmaisesta kolmiosta, jossa molempien kateettien pituus on n, ja lisäksi siinä on n puolikasta yksikköneliötä. Pinta-ala on siten 0.5n^2 0.5n = n(n 1)/2.

Hyvä tapa johtaa kaava on tarkastella summaa rekursioyhtälön kautta. Kun f(n) kuvaa summaa, jossa on laskettu yhteen n ensimmäistä positiivista kokonaislukua, pätee luonnollisesti f(n) - f(n-1) = n.

Tavoitteena on siis löytää funktio, joka toteuttaa rekursiokaavan f(x)-f(x-1) = x ja alkuehdon f(1) = 1. Derivoimalla saadaan f'(x)-f'(x-1) = 1, eli derivaatan arvo kasvaa yhdellä yksiköllä, kun funktion arvo kasvaa yhdellä yksiköllä kuten muotoa f'(x) = x C olevat suorat. Integroimalla kertaalleen saadaan yrite f(x) = 0.5x^2 Cx ja ehdosta f(1) = 1 ratkeaa C = 0.5.

Lopuksi on vielä hyvä todeta, että f(x) = 0.5x^2 0.5x on haluttu ratkaisu. Selvästi f(1) = 1 ja rekursioyhtälö pätee, joten saatu lauseke on oikea.

Eräs kaikkien tuntema tapa on kirjoittaa (n 1)^2-1 = (n 1)^2-n^2 n^2 - (n-1)^2 (n-1)^2 ... 2^2 - 1^2. Summassa jokainen neliö väliltä 2, ..., n-1 esiintyy siis sekä positiivis- että negatiivismerkkisenä.

Koska (a 1)^2 - a^2 = 2a 1, tarkastelemalla oikean puolen termejä pareittain, voidaan todeta, että siinä summataan muotoa 2a 1 olevia termejä, kun a käy läpi luvut 1,2,...,n. Termien 2a summaamisesta kertyy kysytty summa kaksinkertaisena ja ykkösistä tulee vielä n ylimääräistä. Siten vähentämällä n vasemman puolen lausekkeesta ja jakamalla kahdella saadaan vastaus ((n 1)^2-1 - n) / 2 = n(n 1)/2.

Pulmalla on selvä yhteys geometriseen summaan, mikäli tämän kaava oletetaan todistetuksi ensin. Kun x = 1, funktion f(x) = 1 2x 3x^2 ... nx^(n-1) arvo on f(1) = 1 2 3 ... n. Eräs funktion f integraalifunktioista on F(x) = 1 x x^2 ... x^n. Tämä on geometrinen summa, joka voidaan siten ilmaista myös muodossa F(x) = (1-x^n) / (1-x).

Derivoimalla päädytään takaisin esitykseen f(x) = (-nx^(n-1) (n-1)x^n 1) / (1-x)^2. Koska f(x) on jatkuva funktio, myös tästä esitystavasta on saatava laskettua f(1), kun tarkastellaan raja-arvoa, kun x-> 1.

Käyttämällä L'Hôpitalin sääntöä kahdesti sijoittaen x = 1, osoittajaan saadaan n(n 1) ja nimittäjään 2, eli f(1) = n(n 1)/2. Lähestymistapa yhdistää siis summan geometriseen summaan, joskin välivaiheita voidaan pitää todistettavaa asiaa mutkikkaampina.

Pascalin kolmiosta löytyy kaikki kolmioluvut nätisti järjestyksessä, ja kolmiosta näkeekin summan olevan nCr(n 1, n-1). Kaava voidaan siten johtaa binomikertoimien avulla.

Koska i = nCr(i, i - 1) ja 1 = nCr(2, 0), pätee 1 2 3 ... n = nCr(2, 0) nCr(2, 1) nCr(3, 2) nCr(4, 3) ... nCr(n, n-1).

Nyt summa purkautuu, kun Pascalin sääntöä nCr(n, k-1) nCr(n, k) = nCr(n 1, k) käytetään n-1 kertaa. Näin on, sillä ensimmäisen kahden kertoimen summa on nCr(3, 1) ja edelleen nCr(3, 1) nCr(3, 2) = nCr(4, 2), jonka jälkeen nCr(4, 2) nCr(4, 3) = nCr(5, 3), kunnes viimeisellä operoinnilla saadaan nCr(n, n-2) nCr(n, n-1) = nCr(n 1, n-1).

Lopuksi voidaan vielä avata nCr(n 1, n-1) = nCr(n 1, 2) = n(n 1)/2.

Geometrisesti tulos havaitaan suorakulmioiden kautta. Kun tarkastellaan summaa 2 4 6 ... 2n, jokainen summattava voidaan visualisoida 2 * x suorakulmiona.

Kun suorakulmioita liitetään vuorotellen leveys että pituussuunnassa toisiinsa, syntyvä kuvio on aina suorakulmio. Alla on havainnollistettu liittämisprosessia neljän ensimmäisen palan kohdalta, kun numerot kuvaavat palikan kokoa.

22

22
44
44

2266
4466
4466


2266
4466
4466
8888
8888

Huomattavaa on, että kun kuviossa on k = 1 pala, sivujen pituudet ovat k ja k 1. Aina kun uusi kokoa 2 * (k 1) oleva pala liitetään, se voidaan asettaa limittäin sivua vasten jonka pituus on k 1. Tällöin lyhyempi sivu pitenee kahdella yksiköllä ja pidempi pysyy ennallaan, jolloin uudet mitat ovat k 2 ja k 1. Siten millä tahansa luvulla n = k 1, suorakulmion mitat ovat n ja n 1 ja uuden kokoa 2*(n 1) olevan palan liittäminen on mahdollista. Siispä paloista, joiden koot ovat 2, 4, ..., 2n, koostuvan suorakulmion ala on n(n 1).

Koska pinta-ala vastaa summaa 2 4 6 ... 2n = 2*(1 2 3 ... n), summan 1 2 3 ... n arvo on n(n 1)/2.

Hauska tapa todistaa asia on erotella summasta parilliset ja parittomat luvut.

Summa S(2n) = 1 2 ... 2n = 1 3 5 ... (2n-1) 2 4 6 ... 2n.

Nyt parittomien lukujen summa on aina neliöluku n^2. Kahden peräkkäisen neliöluvun k^2 ja (k 1)^2 erotus on nimittäin 2k 1, ja kuten summasta nähdään, neliölukuun n^2 lisättäisiin seuraavassa vaiheessa aina 2n 1, jolloinka ominaisuus säilyy.

Parillisten lukujen summa vastaa parittomien lukujen summaa, kun jokaista lukua on kasvatettu ykkösellä, jolloin summa on n^2 n.

Parillinen ja pariton summa laskettuna yhteen on siis S(2n) = n^2 n^2 n = 2n^2 n, ja korvaamalla luku n luvulla 0.5 n saadaan S(n) = 0.5n^2 0.5n. Jos n olisi pariton, vastaavasti S(2n 1) = S(2n) 2n 1 jolloin sama tulos pätee.

Paraabelin ominaisuuksista tiedetään, että paraabelin S(n) = an^2 bn c kasvuvauhti 2an b riippuu lineaarisesti luvusta n. Koska summan kasvunopeus kasvaa lineaarisesti, kun n kasvaa, on helppo ymmärtää, että kannattaa etsiä sopivaa paraabelia. Jäljelle jää enää löytää sopivat kertoimet a, b ja c. Koska S(0) = 0, c = 0. Koska S(1) = 1, a b = 1 ja koska S(2) = 3, 4a 2b = 3. Yhtälöpari toteutuu, kun a = b = 0.5.

Sama logiikka toimii yleisemmin summan 1^k 2^k ... n^k laskemiseen. Tavoitteena on löytää k 1 asteinen polynomi sopivilla kertoimilla, jolloin kasvuvauhtia kuvaava polynomi on k-asteinen. Ratkaisemalla yhtälöryhmä tarkastellen summaa, kun n = 0, 1, 2, ..., k 1, saadaan oikea lauseke.

Tässä videossa, johon satuin törmäämään, on esitelty 12 tapaa: https://www.youtube.com/watch?v=eHbtc50-qXo

Kaikkihan tuon osaa todistaa, jos on vähän matematiikkaan perehtynyt.

Mikä omasta mielestä on ollut kiintoisaa, on kuinka tuo linkittyy integraalin kaavaan. Eli kun n lähestyy ääretöntä lähestytään kaavaa (1/2) * n^2