Bruðlað með margliðum

Ég var að muna eftir svolítið sniðugu trikki sem kom upp í vinnunni í sumar; þar var ég að forrita í Matlab fyrir tölulega greiningu, svo það er sennilega frekar takmarkaður hópur sem kann að meta þetta, en samt.

Alla vega. Þið vitið þegar maður er að finna gildi endanlegu summunar

1^k + 2^k + 3^k + ... + n^k

fyrir fast k > 0 sem fall af n? Ef maður, af einhverjum ástæðum, langar virkilega að finna formúluna fyrir henni, hefur ekki aðgang að internetinu eða uppflettiritum, og hefur annað hvort tölvu eða þónokkurn frítíma, þá getur maður gert eftirfarandi:

1. Sannfært sjálfan sig um að fallið

f(n) = 1^k + 2^k + 3^k + ... + n^k

sé margliða af stigi k+1. Það er ekkert svo erfitt að sjá að fallið f er O(k+1), því augljóslega er sérhver liður j^k <= n^k, og því

f(n) <= n * n^k = n^(k+1)

Það er samt erfiðara að sanna að f sé margliða, án þess að reikna beint út formúlu fyrir því. En alla vega;

2. Reiknað út gildi f í (k+1)-num punkti. Ég mæli með að byrja á n = 0 og n = 1, og reikna svo n = 2, ..., k, því það liggur alveg sæmilega beint við.

3. Reiknað út stuðla margliðunnar p sem brúar f í punktunum sem valdir voru, og einfalda svo ef maður er í þannig stuði.

Þá er það komið; ef maður vill finna f(n) reiknar maður bara p(n), sem er nokkuð fljótlegra en að reikna j^k fyrir j = 1, ..., n og leggja svo allt draslið saman.

Auðvitað er þetta vita gagnslaust í daglega lífinu, því maður lendir aldrei nokkur tímann í að þurfa að finna gildi þessarar summu, og ef maður þarf þess nauðsynlega er næstum örugglega fljótlegra að (bítur saman tönnum) reikna það með ofbeldi.

En þú veist, ef maður er á eyðieyju eða eitthvað, og hittir eitthvað sem var einu sinni hobbiti sem býr í helli og hefur gríðarlegann áhuga á stærðfræði, og mann vantar eitthvað til að halda honum uppteknum svo hann éti mann ekki meðan maður flýr með hringinn hans, þá er örugglega fínt að grípa til þessa.