Jedan FI zadatak sa dva rjesenja

[kikach]

Molim da mi netko pomogne rijesiti ovaj zadatak:

Neka je funkcija izvodnica za niz (an)neN dana sa

A(x)=(1+x+x^2)^m

Odredite a1 + a3 + a5 + ...(tj. odredite sumu članova niza s neparnim indexima)

[ahri]

evo mog rjesenja. nije najelegantnije, ali pali. razne djelove zadatke se na mnogo nacina moglo rjesiti, ali ja sam birao ove, radi (meni) jednostavnijeg puta.

definirao sam
x[n] = suma svih neparnih za m=n
y[n] = suma svih parnih za m=n
(x[n] je rjesenje)

za x[n+1] vrijedi da je jednak sljedecem:
kada se "m" poveca za jedan (dakle, sa n na n+1) mnozimo sve sa (1+x+x^2).
dakle x[n+1] = x[n] (zato jer mnozimo sve te neparne sa 1, pa ostanu isti, pa je suma ista) + y[n] (jer mnozimo sve parne sa x, pa postanu neparni, pa se suma pribraja!) + x[n] (jer mnozimo sve neparne sa x^2, pa ostanu neparni, dakle suma se pribraja!)

dakle
x[n+1]=x[n] + y[n] + x[n] = 2x[n] + y[n]

jednakim zakljucivanjem (ostajanje parnosti - x^2k * x^2 = x^2(k+1) sto je parno... dakle, mnozenje polinoma s parnim potencijama sa x^2 potencije ostaju parne, mnozenjem sa x postaju neparne etc. - isto zakljucivanje kao i gore) dobivamo
y[n+1]=2y[n] + x[n].

prvo sto sam htio reci je da se ovo sada moze rjesiti kako se rjesava bilo kakva dvostruka rekurzija. ova je cak linearna i lijepa.
no, idemo to sredit ;). ja sam sad ovo malo raspisao i vidio da je y[n]=x[n]+1. idemo to dokazati.

y[n+1] - x[n+1] = 2y[n]+x[n] - 2x[n] - y[n] = y[n] - x[n].
dakle, razlika ovih clanova je stalno ista, pa je jednaka pocetnima.

pocetni uvjeti su (uvrsti se m=1) da su x[1]=1, y[1]=2

so, y[n]=x[n]+1
pa uvrstavanjem u formulu za x[n+1] dobivamo
x[n+1]=3x[n]+1

e sad je to laganini linearna rekurzijica, koja je rjesiva.

no, u ovom trenutku mozemo otici malo perverznije, i vidjeti kako to jos mozemo rjesiti ;). to za dz [(c) of Veky].

lagano se vidi da je suma svih a[1]..a[2m] (to su svi koeficijenti polinoma) jednaka 3^m. to se vidi sto imamo m zagrada sa 3 elementa kojima su koeficijenti 1, pa kada se sve izmnozi imamo 3^m pribrojnika s koeficijentima 1. :)
dakle, x[n] + y[n] = 3^n
a znamo da je y[n]=x[n]+1
pa imamo da je
2x[n] + 1 = 3^n
pa je x[n]=(3^n -1)/2 sto je rjesenje zadatka.


dakle, za n=m, suma svih neparnih je (3^m - 1)/2

dakle, od perverzije back to basic mathematics. no recursions. :)

enjoy ;)

_________________

[veky]

[ahri]

nije lose.
dobije se isto. :)
samo si jos moram posloziti zasto bi A(-1) bila alternatirajuca suma svih. vrijedi za binomne, no nisam bas uvjeren da radi i za sve ostale polynomeke.
no, posto se dobije isto, valjda je oke ;).

p.s. ovime cu smatrati da mi nisi nasao neki divlji bug. woopie-ya-hoo! :)

edit: dokazao za A(-1). idem zaspat. noc :)

_________________

[veky]

[ahri]

pa editirao sam da sam se sjetio, ZBM! :). ja sam to malo drukcije ;)

_________________

[veky]

[ahri]

not kompliciranije!
intuitivnije i jednostavnije. :)

_________________

[ZELENIZUBNAPLANETIDOSADE]

The truth is in the eye of the beholder, I see...

_________________

Pupoljak nije negiran. Rekao sam to i ponovit cu to jos jedanput. Pupoljak NIJE negirAn.
MADD
(Mothers Against Dirty Dialectics)
Based on a true story. NOT.
Ko ih sljivi, mi sviramo punk

[krcko]

Ovaj ahrijev plemeniti pokusaj rjesavanja i vekyjev jos plemenitiji skoro je zavrsio daleko od svoje postojbine. Hvala Odinu sto nam se vratio! Hvala ahriju i vekyju! Vi ste moji idoli!

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.