| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
meri
Gost
|
 Postano: 10:28 uto, 3. 2. 2004 Naslov: jos dva zadatka |
    |
|
|
Imam problema sa rekurzijama i bila bih vrlo zahvalna kad bi mi netko rijesio,tj.dao ideju za sljedeca 2 zadatka(iz rokova):
1. Zadan je niz x1,...,xn pocetnim uvjetima x1=x2=1 i (xn+2)=14(xn+1)- xn-4,n>=1(n,n+1,n+2 su indeksi). Dokazati da je svaki clan tog niza potpun kvadrat.
2.a0=m,m prirodan broj.
an=(-m/n)*(suma po k-ovima od 0 do n-1)ak
Izracunaj: (suma po k-ovima od 0 do m)2^k*ak.
:( :( :(
Da li smijemo na pismenom imati papir sa formulama kao obicno?
Imam problema sa rekurzijama i bila bih vrlo zahvalna kad bi mi netko rijesio,tj.dao ideju za sljedeca 2 zadatka(iz rokova):
1. Zadan je niz x1,...,xn pocetnim uvjetima x1=x2=1 i (xn+2)=14(xn+1)- xn-4,n>=1(n,n+1,n+2 su indeksi). Dokazati da je svaki clan tog niza potpun kvadrat.
2.a0=m,m prirodan broj.
an=(-m/n)*(suma po k-ovima od 0 do n-1)ak
Izracunaj: (suma po k-ovima od 0 do m)2^k*ak.
Da li smijemo na pismenom imati papir sa formulama kao obicno?
|
|
| [Vrh] |
|
veky
Forumaš(ica)
Pridružen/a: 09. 12. 2002. (19:59:43)
Postovi: (5B0)16
Lokacija: negdje daleko...
|
| Postano: 16:40 uto, 3. 2. 2004 Naslov: Re: jos dva zadatka |
|
|
|
[quote="meri"]Imam problema sa rekurzijama i bila bih vrlo zahvalna kad bi mi netko rijesio,tj.dao ideju za sljedeca 2 zadatka(iz rokova):
1. Zadan je niz x1,...,xn pocetnim uvjetima x1=x2=1 i (xn+2)=14(xn+1)- xn-4,n>=1(n,n+1,n+2 su indeksi). Dokazati da je svaki clan tog niza potpun kvadrat.[/quote]
Rješenje je prilično jednostavno, jednom kad znaš kvadrat _čega_ to jest. Rješenje "iz vedra neba" je npr. ovo:
promotrimo rekurziju y_(n+2)=4y_(n+1)-y_n , s početnim uvjetima y_1=y_2=1 . Lako se vidi (matematička indukcija s bazom {1,2} ) da je x_n=(y_n)^2 , a y_n je cijeli broj.
Naravno, sumnjam da ti to rješenje puno pomaže, jer ne znaš kako doći do rekurzije za y-e in the first place. Poanta je gledati karakterističnu jednadžbu (homogene rekurzije), odnosno njene korijene. Ovdje se radi o lam^2-14lam+1=0 , odnosno o 7+-4sqrt(3) . Sad, jer je 7-4sqrt(3) prilično mali broj, x_n je otprilike nekakonstanta*(7+4sqrt(3))^n . Ako nasilno izvadimo korijen iz toga, dobijemo da bi ono od čega bi x_n trebao biti kvadrat trebalo biti otprilike nekadrugakonstanta*(2+sqrt(3))^n (malim namještanjem se vidi da je sqrt(7+4sqrt(3))=2+sqrt(3) . To bi onda moglo biti veće rješenje karakteristične jednadžbe za y-e . Drugo je onda vjerojatno 2-sqrt(3) (želimo da koeficijenti budu cijeli brojevi), pa jednadžba glasi lam^2-4lam+1=0 , iz čega se lako dobije rekurzija. Naravno, sve ovo je čista heuristika koja nema veze sa strogošću, pa bi stvar trebalo i dokazati... no kao što rekoh, jednom kad se ima rekurzija, to lako ide math-indukcijom.
[quote]2.a0=m,m prirodan broj.
an=(-m/n)*(suma po k-ovima od 0 do n-1)ak
Izracunaj: (suma po k-ovima od 0 do m)2^k*ak.[/quote]
Ovdje ipak treba malo raspisivati (prvih par članova a-niza), i sređivati izraze... ili pak poznavati binomne koeficijente kao svoj džep. :-)
nakon što se dobije a_0 , a_1 , a_2 i a_3 , trebalo bi biti vidljivo da a_n=m*(m povrh n)*(-1)^n zvuči kao prilično razumna hipoteza. Naravno, to se sad dokaže bez većih problemâ, a ova suma što se traži po binomnom teoremu bude jednaka m*(2-1)^m=m .
HTH,
| meri (napisa): | Imam problema sa rekurzijama i bila bih vrlo zahvalna kad bi mi netko rijesio,tj.dao ideju za sljedeca 2 zadatka(iz rokova):
1. Zadan je niz x1,...,xn pocetnim uvjetima x1=x2=1 i (xn+2)=14(xn+1)- xn-4,n>=1(n,n+1,n+2 su indeksi). Dokazati da je svaki clan tog niza potpun kvadrat. |
Rješenje je prilično jednostavno, jednom kad znaš kvadrat _čega_ to jest. Rješenje "iz vedra neba" je npr. ovo:
promotrimo rekurziju y_(n+2)=4y_(n+1)-y_n , s početnim uvjetima y_1=y_2=1 . Lako se vidi (matematička indukcija s bazom {1,2} ) da je x_n=(y_n)^2 , a y_n je cijeli broj.
Naravno, sumnjam da ti to rješenje puno pomaže, jer ne znaš kako doći do rekurzije za y-e in the first place. Poanta je gledati karakterističnu jednadžbu (homogene rekurzije), odnosno njene korijene. Ovdje se radi o lam^2-14lam+1=0 , odnosno o 7+-4sqrt(3) . Sad, jer je 7-4sqrt(3) prilično mali broj, x_n je otprilike nekakonstanta*(7+4sqrt(3))^n . Ako nasilno izvadimo korijen iz toga, dobijemo da bi ono od čega bi x_n trebao biti kvadrat trebalo biti otprilike nekadrugakonstanta*(2+sqrt(3))^n (malim namještanjem se vidi da je sqrt(7+4sqrt(3))=2+sqrt(3) . To bi onda moglo biti veće rješenje karakteristične jednadžbe za y-e . Drugo je onda vjerojatno 2-sqrt(3) (želimo da koeficijenti budu cijeli brojevi), pa jednadžba glasi lam^2-4lam+1=0 , iz čega se lako dobije rekurzija. Naravno, sve ovo je čista heuristika koja nema veze sa strogošću, pa bi stvar trebalo i dokazati... no kao što rekoh, jednom kad se ima rekurzija, to lako ide math-indukcijom.
| Citat: | 2.a0=m,m prirodan broj.
an=(-m/n)*(suma po k-ovima od 0 do n-1)ak
Izracunaj: (suma po k-ovima od 0 do m)2^k*ak. |
Ovdje ipak treba malo raspisivati (prvih par članova a-niza), i sređivati izraze... ili pak poznavati binomne koeficijente kao svoj džep. 
nakon što se dobije a_0 , a_1 , a_2 i a_3 , trebalo bi biti vidljivo da a_n=m*(m povrh n)*(-1)^n zvuči kao prilično razumna hipoteza. Naravno, to se sad dokaže bez većih problemâ, a ova suma što se traži po binomnom teoremu bude jednaka m*(2-1)^m=m .
HTH,
|
|
| [Vrh] |
|
meri
Gost
|
| Postano: 20:06 uto, 3. 2. 2004 Naslov: |
|
|
|
Ajme izgleda da meni puno previse toga nije ocito, a na ispitu ce mi biti jos manje. Ja sam raspisivala te clanove do petoga, ali zbilja nista nisam vidjela, ali kada kazete, to zbilja jesu binomni koeficijenti. Hvala.
Onaj prvi, ajoj, i dalje mi bas nije bistro. :( :( :( :(
Ajme izgleda da meni puno previse toga nije ocito, a na ispitu ce mi biti jos manje. Ja sam raspisivala te clanove do petoga, ali zbilja nista nisam vidjela, ali kada kazete, to zbilja jesu binomni koeficijenti. Hvala.
Onaj prvi, ajoj, i dalje mi bas nije bistro.
|
|
| [Vrh] |
|
veky
Forumaš(ica)
Pridružen/a: 09. 12. 2002. (19:59:43)
Postovi: (5B0)16
Lokacija: negdje daleko...
|
| Postano: 22:40 uto, 3. 2. 2004 Naslov: |
|
|
|
[quote="meri"]Ajme izgleda da meni puno previse toga nije ocito, a na ispitu ce mi biti jos manje. Ja sam raspisivala te clanove do petoga, ali zbilja nista nisam vidjela, ali kada kazete, to zbilja jesu binomni koeficijenti. Hvala.[/quote]
Ma nije tako strašno. Probaj faktorizirati čudne polinome koje dobiješ, često pomaže. ;-)
Da si shvatila da u a_3 imaš m^2(m-1)(m-2) , garant bi u a_4 već vidjela da imaš m^2(m-1)(m-2)(m-3) , a to je (bez jednog m i predznaka) padajuća potencija koja se baš lijepo slaže s onim faktorijelama u nazivniku (faktorijele si primijetila valjda?).
[quote]Onaj prvi, ajoj, i dalje mi bas nije bistro. :( :( :( :([/quote]
Što - dokaz indukcijom da su xevi kvadrati yova , ili kako smo do y-ova došli? Ovo prvo bi stvarno trebalo biti jasno, a drugo je posljedica opće formule za rješenje linearne rekurzije. Ako su rješenja karakteristične jednadžbe lam1 i lam2 (različita), tad je opći oblik rješenja homogene rekurzije x_n=C1*lam1^n+C2*lam2^n . Ak je produkt lamova:-) 1 , logicno je da ce jedan od njih na n-tu ici u beskonacnost i odredivati velicinu x_n-a , dok ce drugi ici u 0 . E sad iz ovog većeg izvadiš korijen i nadaš se da si na taj način zaista dobila nešto iz čega možeš rekonstruirati rekurziju čija će rješenja biti korijeni x-eva. Okej?
| meri (napisa): | | Ajme izgleda da meni puno previse toga nije ocito, a na ispitu ce mi biti jos manje. Ja sam raspisivala te clanove do petoga, ali zbilja nista nisam vidjela, ali kada kazete, to zbilja jesu binomni koeficijenti. Hvala. |
Ma nije tako strašno. Probaj faktorizirati čudne polinome koje dobiješ, često pomaže. 
Da si shvatila da u a_3 imaš m^2(m-1)(m-2) , garant bi u a_4 već vidjela da imaš m^2(m-1)(m-2)(m-3) , a to je (bez jednog m i predznaka) padajuća potencija koja se baš lijepo slaže s onim faktorijelama u nazivniku (faktorijele si primijetila valjda?).
| Citat: | | Onaj prvi, ajoj, i dalje mi bas nije bistro. |
Što - dokaz indukcijom da su xevi kvadrati yova , ili kako smo do y-ova došli? Ovo prvo bi stvarno trebalo biti jasno, a drugo je posljedica opće formule za rješenje linearne rekurzije. Ako su rješenja karakteristične jednadžbe lam1 i lam2 (različita), tad je opći oblik rješenja homogene rekurzije x_n=C1*lam1^n+C2*lam2^n . Ak je produkt lamova:-) 1 , logicno je da ce jedan od njih na n-tu ici u beskonacnost i odredivati velicinu x_n-a , dok ce drugi ici u 0 . E sad iz ovog većeg izvadiš korijen i nadaš se da si na taj način zaista dobila nešto iz čega možeš rekonstruirati rekurziju čija će rješenja biti korijeni x-eva. Okej?
|
|
| [Vrh] |
|
meri
Gost
|
|
| [Vrh] |
|
krcko
Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
|
| Postano: 0:11 sri, 4. 2. 2004 Naslov: Re: jos dva zadatka |
|
|
|
[quote="veky"]Ovdje ipak treba malo raspisivati (prvih par članova a-niza), i sređivati izraze... ili pak poznavati binomne koeficijente kao svoj džep. :-)[/quote]
Ili znati rjesavati rekurzije pomocu funkcija izvodnica 8)
[quote="veky"]nakon što se dobije a_0 , a_1 , a_2 i a_3 , trebalo bi biti vidljivo da a_n=m*(m povrh n)*(-1)^n zvuči kao prilično razumna hipoteza.[/quote]
Evo kako se do toga dodje direktno. Neka je f(x) funkcija izvodnica niza a_n, tj. f(x)=\sum a_n x^n. Pitamo se kako doci do sume a_n-ova... :idea: Ideja je pomnoziti f(x) sa geometrijskim redom, tj. 1/(1-x). Dobije se f(x)/(1-x)=\sum (a_0+a_1+...a_n) x^n. Iz rekurzije se vidi da koeficijent mozemo izraziti kao -(n+1)a_(n+1)/m, pa dobijemo zapravo ovo:
[code:1]f(x)/(1-x)=-f'(x)/m[/code:1]
Sad, to je diferencijalna jednadzba za f(x) :shock: ali jako lagana za rijesiti \:D/ Pocetni uvjet je f(0)=a_0=m, separiramo varijable, integriramo /blablabla :prodike: / i dobijemo f(x)=m(1-x)^m. Iz tog se pomocu binomnog teorema odmah vidi vekyjeva formula za a_n, ali ona ti zapravo ne treba. Kao bonus za koristenje FI, onu sumu koju treba izracunati na kraju dobije se obicnim uvrstavanjem f(2) = m*(-1)^m.
| veky (napisa): | | Ovdje ipak treba malo raspisivati (prvih par članova a-niza), i sređivati izraze... ili pak poznavati binomne koeficijente kao svoj džep. |
Ili znati rjesavati rekurzije pomocu funkcija izvodnica 
| veky (napisa): | | nakon što se dobije a_0 , a_1 , a_2 i a_3 , trebalo bi biti vidljivo da a_n=m*(m povrh n)*(-1)^n zvuči kao prilično razumna hipoteza. |
Evo kako se do toga dodje direktno. Neka je f(x) funkcija izvodnica niza a_n, tj. f(x)=\sum a_n x^n. Pitamo se kako doci do sume a_n-ova...  Ideja je pomnoziti f(x) sa geometrijskim redom, tj. 1/(1-x). Dobije se f(x)/(1-x)=\sum (a_0+a_1+...a_n) x^n. Iz rekurzije se vidi da koeficijent mozemo izraziti kao -(n+1)a_(n+1)/m, pa dobijemo zapravo ovo:
Sad, to je diferencijalna jednadzba za f(x)  ali jako lagana za rijesiti  Pocetni uvjet je f(0)=a_0=m, separiramo varijable, integriramo /blablabla  / i dobijemo f(x)=m(1-x)^m. Iz tog se pomocu binomnog teorema odmah vidi vekyjeva formula za a_n, ali ona ti zapravo ne treba. Kao bonus za koristenje FI, onu sumu koju treba izracunati na kraju dobije se obicnim uvrstavanjem f(2) = m*(-1)^m.
_________________
Vedran Krcadinac
Ljudi su razliciti, a nula je paran broj.
|
|
| [Vrh] |
|
krcko
Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
|
|
| [Vrh] |
|
veky
Forumaš(ica)
Pridružen/a: 09. 12. 2002. (19:59:43)
Postovi: (5B0)16
Lokacija: negdje daleko...
|
|
| [Vrh] |
|
defar
Forumaš(ica)
Pridružen/a: 19. 01. 2004. (01:37:19)
Postovi: (152)16
|
| Postano: 17:42 uto, 1. 2. 2005 Naslov: |
|
|
|
aaahaaaaaaaaaaaaaaaaaaaaaaaa! radi se o sumi (2^k)*a_k po k, a ne 2^(k*a_k), zar ne? :oops:
aaahaaaaaaaaaaaaaaaaaaaaaaaa! radi se o sumi (2^k)*a_k po k, a ne 2^(k*a_k), zar ne? 
_________________
`To begin with, a dog's not mad. You grant that? 'Well, then,' the Cat went on, `you see, a dog growls when it's angry, and wags its tail when it's pleased. Now I growl when I'm pleased, and wag my tail when I'm angry. Therefore I'm mad.'
|
|
| [Vrh] |
|
krcko
Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
|
|
| [Vrh] |
|
veky
Forumaš(ica)
Pridružen/a: 09. 12. 2002. (19:59:43)
Postovi: (5B0)16
Lokacija: negdje daleko...
|
|
| [Vrh] |
|
defar
Forumaš(ica)
Pridružen/a: 19. 01. 2004. (01:37:19)
Postovi: (152)16
|
| Postano: 17:53 sri, 2. 2. 2005 Naslov: |
|
|
|
eh, da. a ja sam prvo mislila da pise ovo drugo, i jos se neko vrijeme uspjela cudit' kako to tebi sliedi direktno iz binomnog teorema, a krcku je to jednako f(2). mislim, kolko blesav covjek moze bit i zivit' ovoliko dugo koliko ja vec zivim?:)
eh, da. a ja sam prvo mislila da pise ovo drugo, i jos se neko vrijeme uspjela cudit' kako to tebi sliedi direktno iz binomnog teorema, a krcku je to jednako f(2). mislim, kolko blesav covjek moze bit i zivit' ovoliko dugo koliko ja vec zivim?
_________________
`To begin with, a dog's not mad. You grant that? 'Well, then,' the Cat went on, `you see, a dog growls when it's angry, and wags its tail when it's pleased. Now I growl when I'm pleased, and wag my tail when I'm angry. Therefore I'm mad.'
|
|
| [Vrh] |
|
|
