Rekurzivna relacija - zadaca

[Androxism]

Pozdrav forumaši!

Evo imam opet problema sa zadaćom pošto nam zadaju takvu da nismo radili još to gradivo pa... Da li bi mi mogli pomoći rješiti sljedeći zadatak:

Riješite rekurzivnu relaciju: 3^n * an + 3^(n-1) * a(n-1) = 8, a1 = 1.
(Uputa: koristi se supstitucija.)

Napomena: kod an i a(n-1) su n i n-1 indeksi


Unaprijed hvala!

[goranm]

Neka je [tex]b_n=3^na_n[/tex]. Tada je [tex]b_1=3[/tex] i još je [tex]b_n+b_{n-1}=8[/tex], tj. [tex]b_n=8-b_{n-1}[/tex].

Prvih nekoliko vrijednosti za [tex]b_n[/tex] su:

[tex]
b_2=8-b_1=5[/tex]
[tex]b_3=8-b_2=3[/tex]
[tex]b_4=8-b_3=5[/tex]
[tex]b_5=8-b_4=3[/tex]
[tex]\vdots[/tex]

Pretpostavimo da je [tex]b_n=(-1)^n+4[/tex] rješenje rekurzije i to dokažemo indukcijom. Prema tome, [tex]a_n=3^{-n}(4+(-1)^n).[/tex]

_________________
The Dude Abides

[Androxism]

a zasto imamo bn + bn-1 = 8 kad tog nigdje nemam u zadanoj formuli? :S

[goranm]

Ako je [tex]3^n a_n + 3^{n-1} a_{n-1} = 8[/tex] rekurzivna jednadžba i ako je [tex]b_n=3^na_n[/tex] supstitucija, onda je [tex]b_{n-1}=3^{n-1}a_{n-1}[/tex] pa je [tex]b_n+b_{n-1}=8[/tex].

_________________
The Dude Abides

[Androxism]

Aha, znaci i za drugi dio si iskoristio supstituciju. Ok hvala, razumijem taj dio sad. Znaci ja moram dobit time vrijednost an koji bi vrijedio za tu jednadzbu=8? a koji je opceniti princip rjesavanja rekurzije u kombinatorici?

[goranm]

[inber]

pozdrav,
trebala bi mi pomoć oko jednaog zadatka... naletila sam slucajno na ovaj forum... pa ako bi mi kolege iz Zagreba ikako mogle pomoci..


Broj bakterija u nekoj bakterijskoj kulturi je približno 2000 i taj se broj
svakih 2 sata povečava 300 posto. Odredite pogodnu rekurzivnu relaciju,
te pomoću nje nadite broj bakterija u toj kulturi nakon dva dana.

hvala.

[krcko]

"Povecava 300 posto" znaci ovo

ili ovo?

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.

[goranm]

Ovo drugo. Da piše povećava 50%, onda bi po prvom ispalo da se svaki sat prepolovi broj bakterija.

_________________
The Dude Abides

[Androxism]

Ovaj, jos jedno pitanje, nije mi jasno od kud smo pretpostavili ovo:

Pretpostavimo da je bn=(-1)+4 rješenje rekurzije i to dokažemo indukcijom.


i otkuda smo dobili onda u an članu 3^-n?

[goranm]

[inber]

hvala na odgovoru...
riješila sam zadatak na malo drugaciji nacin ali uspješno...

[krcko]

Ne kuzim kako se moze rijesiti na drugi nacin Broj 2000 se pomnoži s nešto^24, gdje je nešto 3 ili 4.

@goranm: za Pravog Matematicara(TM) "povecanje" moze biti i smanjenje. Samo ekonomisti na taj nacin cjepidlace oko terminologije

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.

[inber]

evo ovako sam rjesila, nadam se da je ipak 3^24*2000 a ne ona druga opcija 4^24*2000.

[tex]B_{1}=3B_{0}[/tex]

[tex]B_{2}=3B_{1}[/tex]
...

[tex]B_{n+1}=3B_{n}[/tex]

tj da je
[tex]B_{n}=3^nB_{0}[/tex]

[krcko]

Osim u oznaci (a / B), u cemu je razlika?

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.

[Androxism]

da li mi mozes jos dokaz pokazati za indukciju?

Added after 2 minutes:

da li mi mozes jos dokaz pokazati za indukciju?

[goranm]

Ne treba čak niti indukcija. Jednostavno se pokaže da je [tex]b_1=3 [/tex] i [tex]b_{n}+b_{n-1}=8[/tex] za svaki n.

Ovo prvo očito vrijedi, a ovo drugo treba samo malo raspisat

[tex]b_{n}+b_{n-1}=4+(-1)^n+4+(-1)^{n-1}=8-(-1)^{n-1}+(-1)^{n-1}=8[/tex].

_________________
The Dude Abides

[Androxism]

ma ne to, htio bih dokazati da vrijedi bn=(-1)^n + 4 a ovo je ocito da vrijedi sto si napisao neznam kako to uvrstiti u indukciju i dokazati...

[Megy Poe]

pp da vrijedi bn=(-1)^n+4 i da je 3^nan=bn, sad u početnoj rekurziji umjesto an uvrstiš an+1..i onda an+1 i an izraziš preko bn+1 odnosno bn, pošto si pretpostavio koliko ti je bn umjesto njega uvrstiš (-1)^n+4 i kad se to malo sredi dobit ces koliki je bn+1 tj dokazat ces indukciju.

[anuska_vkci]

Odredite rekurzivnu relaciju za niz (an)n element iz N ako je an:
a) broj nacina na koje mozemo poredati u red n osoba, razlikujuci ih
po spolu,

b) broj nacina na koje mozemo poredati u red n osoba, razlikujuci ih
po spolu, ali tako da dvije osobe muskog spola ne stoje jedna iza
druge.

Može li mi netko ovo riješiti? Ovo mi je zadnja zadaća iz kombinatorike i o njoj mi ovisi hožu li proći kolegij :S Please