Rekurentna jednačina

#fax #math #ds2 [deo kombinatorike]

Opšti oblik rekurentne jednačine -tog reda:

Def.

  • Rešenje rj je bilo koji niz , takav da
    članovi niza zadovoljavaju rj.
  • Opšte rešenje obuhvata sva rešenja rj, tako da je rešenje.
  • Partikularno rešenje je rešenje koje je određeno vrednostima prvih članova niza.

Linearna rekurentna jednačina

Linearna rekurentna jednačina -tog reda:

Vrste:

  • sa konstantnim koeficijentima ()
  • sa funkcionalnim koeficijentima
  • homogena ako ; nehomogena inače
  • normalizovana ako

Stav. Opšte rešenje homogene linearne rj je linearna kombinacija svih nezavisnih rešenja.

Stav. Opšte rešenje nehomogene linearne rj je , gde je opšte rešenje odgovarajuće homogene linearne rj, je neko partikularno rešenje nehomogene linearne rj.

Rešavanje linearne rekurentne jednačine sa konstantnim koeficijentima

  • HOMOGENA

1) Tražimo opšte rešenje :

Pravimo odgovarajuću karakterističnu jednačinu:

koja ima nule između kojih može biti višestrukih.
Tada opšte rešenje je zbir članova, svakom od kojih odgovara jedna nula. Članovi su oblika , gde je to -to pojavljivanje nule , idući redom po nulama i

Ako su sve nule karakteristične jednačine različite,
opšte rešenje je

Ako
opšte rešenje je

2) Tražimo partikularno rešenje u zavisnosti od prvih članova niza (tj određujemo ) tako što ubacujemo redom u opšte rešenje i rešavamo dobijen sistem.

Primer

  • NEHOMOGENA

1) Tražimo opšte rešenje odgovarajuće homogene

2) Tražimo partikularno rešenje nehomogene :

Ako , gde je polinom stepena i
je -struka nula ( ako nije nula) karakteristične jednačine odgovarajuće homogene rj.
Tada ,
brojevi se dobijaju ubacivanjem u polaznu rj.

3) Opšte rešenje

4) Tražimo partikularno rešenje u zavisnosti od prvih članova niza (tj određujemo ) tako što ubacujemo redom u opšte rešenje i rešavamo dobijen sistem.

Primer

Primer 1
Primer 2