Formulės išvedimas iš rekurentinio sąryšio

Sveiki :)

Prireikė pagalbos ir man. Sprendžiu programavimo uždavinį ir gavau f(x) išraišką, kuri priklauso nuo f(x-1), man reikalinga f(x), kuri nepriklauso nuo f(x-1) ar ankstesnių funkcijų rezultatų. Argumentas ir rezultatas yra sveikieji skaičiai.

f(x) = f(x-1) + ∑(i=1, x-1)((i-1)(x-1-i)+1), f(0) = 1.

Ten kur yra suma, tai pirmuose skliausteliuose kintamojo kitimo rėžiai, o antruose - pats reiškinys.

Keletas pirmųjų reikšmių:
0 -> 1,
1 -> 1,
2 -> 2,
3 -> 4,
4 -> 8,
5 -> 16,
6 -> 31.

Už išvedimą būsiu labai dėkingas :)

Sveikas, gal gali pasikeisti savo parašą, žinok labai apkrauna puslapio atidarymą žmonės, kurie turi lėtesnį internetą ;)

VitalijusSveikas, gal gali pasikeisti savo parašą, žinok labai apkrauna puslapio atidarymą žmonės, kurie turi lėtesnį internetą ;)

ShadoWsaZSveiki :)

Prireikė pagalbos ir man. Sprendžiu programavimo uždavinį ir gavau f(x) išraišką, kuri priklauso nuo f(x-1), man reikalinga f(x), kuri nepriklauso nuo f(x-1) ar ankstesnių funkcijų rezultatų. Argumentas ir rezultatas yra sveikieji skaičiai.

f(x) = f(x-1) + ∑(i=1, x-1)((i-1)(x-1-i)+1), f(0) = 1.

Ten kur yra suma, tai pirmuose skliausteliuose kintamojo kitimo rėžiai, o antruose - pats reiškinys.

Keletas pirmųjų reikšmių:
0 -> 1,
1 -> 1,
2 -> 3,
3 -> 4,
4 -> 8,
5 -> 16,
6 -> 31.

Už išvedimą būsiu labai dėkingas :)

AncientMariner
Gal gali dar kartą peržiūrėti sąlygą? Man rodos, f(3) = 5, jei formulė užrašyta teisingai. Nenorėčiau pradėti veltis į skaičiavimus, kurie gali būti ganėtinai negražūs, jei sąlygoje yra klaida (net ir mažos klaidos rekursinėse formulėse dažniausiai visiškai pakeičia skaičiavimus, kuriuos reikia atlikti).

Iš pradžių verta aiškiau susitvarkyti formulę:
[tex]\sum_{i=1}^{x-1} \left ( (i-1)(x-1-i) + 1 \right ) =  \sum_{i=0}^{x-2} \left ( i(x-2-i) + 1 \right ) = \sum_{i=0}^{x-2} i(x-2-i) + (x-2)[/tex]
[tex]f(x) = f(x - 1) + \sum_{i=0}^{x-2} i(x-2-i) + (x-2)[/tex]

Dėl patogumo taip pat pažymėkime g(x) = f(x + 2). Tuomet mes turime
[tex]g(x) = g(x - 1) + \sum_{i=0}^{x} i(x-i) + x[/tex]

Yra triukas, kuris leidžia labai greitai rasti g. Jei p(x) yra n-tojo laipsnio daugianaris, tai yra toks (n+1)-ojo laipsnio daugianaris q(x), kad
[tex] q(x) = \sum_{i=0}^x p(i)[/tex]
su visais sveikais x > 0. Pirma, tai reiškia, kad yra toks trečio laipsnio daugianaris p(x), kad
[tex] p(x) = \sum_{i=0}^{x} i(x-i)[/tex]
Tačiau
[tex]g(x) = g(x-1) + p(x) + x = g(0) + \sum_{i=1}^x \left ( p(i) + i )[/tex]
taigi ir pati funkcija g(x) yra (ne didesnio nei) ketvirto laipsnio daugianaris. Kitaip sakant, yra tokie realūs skaičiai a, b, c, d, e kad
[tex]g(x) = ax^4 + bx^3 + cx^2 + dx + e[/tex]
Žinome, kad g(-2) = f(0) = 1, g(-1) = f(1) = 1, g(0) = f(2) = 2, g(1) = f(3) = 4, g(2) = f(4) = 8.

Turime penkias tiesines lygtis ir iš jų randame koeficientus:
a = 1/24, b = 1/12, c = 11/24, d = 17/12, e = 2.

Negarantuoju, kad nepalikau aritmetikos klaidų, - geriau pasitikrink.

Yra kitas (labiau tiesmukas) sprendimo metodas: galima susumuoti visas eilutes, naudojant formules 1 + 2 + ... + n = (n+1)n/2, 1² + 2² + ... + n² = (2n + 1)(n + 1)n/6, 1³ + 2³ + ... + n³ = ((n+1)n/2)², ir taip gauti (tą patį, jei nėra klaidų) atsakymą.

Dabar viskas pasidarė kur kas aiškiau ir formulė išvesta. Šaunuolis AncientMariner :)
Dėkui, kad skyrei laiko :)