Matematické Fórum

JouiBart · 11. 11. 2009 19:51

Ahoj potřeboval bych poradit jak vyřešit tento příklad, dostal jsem ho ve škole a matematika zrovna není moje silná stránka. Budu rád za každou radu;)

Code:

Je dána funkce f(n) z přirozených do celých čísel tímto rekurentním předpisem:
f(0) = −5
f(n + 1) = 3 · f(n) + 14 · n + 11 pro všechna n ¸ 0
Vašim úkolem je dokázat následující matematickou větu (o naší dané f).
Existuje přirozené n0 takové, že pro všechna n ¸ n0 platí
f(n) · 4 · 3n − 2009 .

Olin · 11. 11. 2009 21:06

Nazdar, nějak není úplně čitelná matika. Čtu správně?
$f(n+1) = 3 f(n) + 14 n + 11$
Ovšem to, co se má dokázat, nedokážu rozluštit tak, aby mi to dávalo smysl.

JouiBart · 11. 11. 2009 22:01

Čteš správně, spočítat to třeba f(5) dokážu,ale nevim jak udělat ten důkaz.

JouiBart

Teďka jsem si všiml že máme ve skriptech vzor jak to zhruba má vypadat.

Code:

Věta. Nechť funkce f pro každé n  0 splňuje vztah f(n + 2) =2f(n + 1) − f(n). 
Pokud platí f(0) = 1 a zároveň f(1) = 2, tak platí f(n) = n + 1 pro všechna přirozená n  0. 

Důkaz: Už samotný pohled na daný vztah f(n + 2) = 2f(n + 1) − f(n) naznačuje, že bychom 
měli rozšířit indukční předpoklad (a krok) zhruba takto:
Pro každé n  0; jestliže platí T(n); neboli f(n) = n + 1, a zároveň platí
T(n + 1); f(n + 1) = n + 2, pak platí také T(n + 2); f(n + 2) = n + 3.

Báze indukce –2 pozor, zde už musíme ověřit dvě hodnoty f(0) = 0 + 1 = 1, f(1) = 1 + 1 = 2 .
Náš indukční krok tak nyní může využít celého rozšířeného předpokladu, znalosti
hodnot f(n) i f(n + 1), pro ověření f(n+2) = 2f(n+1)−f(n) = 2 · (n+1+1)−(n+1) = n+3 = n+2+1 .

melman.fousek · 11. 11. 2009 22:20

zkus to mat. indukci?! Ma-li tvuj vyrok V(n) byt pravdivy, pak musi platit to same pro vyrok V(n+1) nebo ne?! resp. zkus nejdriv dosadit nejake cislo, coz uz jsi udelal a pokud L=P pak prejdu k druhemu kroku a zkus dosadit do puvodniho predpisu misto (n) -> (n+1)

JouiBart

Code:

Je dána funkce f(n) z přirozených do celých čísel tímto rekurentním předpisem:
f(0) = −5
f(n + 1) = 3 * f(n) + 14 * n + 11 pro všechna n ¸ 0
Vašim úkolem je dokázat následující matematickou větu (o naší dané f).
Existuje přirozené n0 takové, že pro všechna n ¸ n0 platí
f(n)<= 4 * 3^n − 2009

Nevim jestli počítám správně,mohl by jste mě to někdo zkontrolovat?
pro n=0
$f(0)<=4*3^0-2009$ = $-5<=-2005$ a to neplatí

$f(n + 1) = 3 * f(n) + 14 * n + 11$ = $f(1)=3 * f(0) + 14 * 1 + 11$ = $f(1)= 3 * (-5) + 14 * 1 + 11$ = $f(1)=10$
pro n+1
$3 * f(n) + 14 * n + 11 <=4 *3(n+1) -2009$ = $3*(-5)+ 14 * 0 + 11 <= 4*3^1 -2009$ = $10<=-1997$

<= je menší nebo rovno

Blizzy · 15. 11. 2009 21:34 — Editoval Blizzy (15. 11. 2009 21:49)

Ta indukce správně není, neplatí přece báze pro n=0.

Můžu se zeptat jak jsi přišel pro které první n (vlastně n0) ta nerovnost platí? Proč právě pro n=5? Zkoušel jsi všechny hodnoty a tohle byla první, která ti vyšla nebo je na to nějaký lepší způsob?

Pokud budeš mít některé n0 pro které to platí, tak můžeš použít výše zmiňovaný způsob dle skript.

btw. v zadání jsou některé znaky špatně, předpokládám, že správné zadání je následující:

Je dána funkce f(n) z přirozených do celých čísel tímto rekurentním předpisem:
$f(0) = -5$
$f(n + 1) = 3 \cdot f(n) + 14 \cdot n + 11$ pro všechna $n \geq 0$

Vašim úkolem je dokázat následující matematickou větu (o naší dané f):

Existuje přirozené $n_0$ takové, že pro všechna $n \geq n_0$ platí
$f(n)\leq 4 \cdot 3^n - 2009$

JouiBart

Takže jestli to chápu dobře tak musím najít takove $n$ pro které to platí?
Nevíte někdo jak to matematicky dokázat? Když to hodim do programu tak po 17-ctým čísle to přeteče.

Kondr · 16. 11. 2009 11:22

↑ JouiBart:Ne, hledáš $n_0$ . S jinými čísly řešeno zde: http://forum.matweb.cz/viewtopic.php?id=11800

kaja(z_hajovny) · 16. 11. 2009 11:40

Zase nejaky automat generuje zadani?

JouiBart · 16. 11. 2009 11:58

Jo na muni.

Kondr · 16. 11. 2009 12:07

↑ kaja(z_hajovny):Zdravím. Ano, opět generátor docenta Hliněného pro předmět Úvod do informatiky aka Induction and recursion.

JouiBart · 16. 11. 2009 12:37

Chápu-li to dobře, tak vemu $f(n + 1) = 3 \cdot f(n) + 14 \cdot n + 11$ a $f(0) = -5$ pujdu na stranku http://www.wolframalpha.com/input/?i=f% … 80%29%3D-5 vemu výsledek a dosadim ho na f(n) takhle $4*3^n-7*n-9$

Hypotéza,že:

Bázový krok:
$f(0)=-5$
$4*3^0-7*0-9=-5$ (*)
Proto pro $n=0$ platí $f(n)=4*3^n-7n-9$ .

Indukční krok: předpokládejme, že $f(k)=4*3^k-7k-9$ a dokažme $f(k+1)=4*3^(k+1)-7(k+1)-9$
Ze zadání $f(k+1)= 3*f(k)+14*k+11$ , dosazením z indukčního předpokladu máme
$f(k+1)= 3(4*3^k-7k-9)+14*k+11$ = $4*3^(k+1)-21k-27+14k+11$ = $4*3^(k+1)-7k-16$ = $4*3^(k+1)-7(k+1)-9$

Tím je hypotéza (*) dokázána.

Akorát jsem nepochopil moc věc stím jak zjistím $n(0)$

JouiBart · 16. 11. 2009 12:39

Ahoj... jj přesně.. Generátor pana Hliněného.

Kondr · 17. 11. 2009 11:38

↑ JouiBart:n_0 stačí zvolit tak, aby bylo -7n_0-9<2009, tedy např. n_0=300.

sealer · 17. 11. 2009 16:12

Rád bych poprsil aspoň pro sběžnou kontrolu mého důkazu....

Je dána funkce $f(n)$ z přirozených čísel do celých čísel tímto rekurentním předpisem: $f(0)=-12$ $f(n+1)=4*f(n)+39*n+44$ pro všechna n=>0
Dokažme: Existuje přirozené číslo n_0 takové, že pro všechna n=>n_0 platí $f(n)<=7*4^n-13*n-19$

Vyslovme hypotézu, že : $f(n)=7*4^n-13*n-19$
ověřme indukcí
Báze:
$f(0)=-12$ $7*4^0-13*0-19=-12$ L=P
proto pro n=0 platí: $f(n)=7*4^n-13*n-19$

Indukční krok:
Za předpokladu, že $f(k)=7*4^k-13*k-19$ dokažme $f(k+1)=7*4^(k+1)-13*(k+1)-19$
Dosadíme indukční předpoklad do zadání:
$f(k+1)=4*(7*4^k-13*k-19)+39*k+44 = 7*4^(k+1)-52*k-76+39*k+44 = 7*4^(k+1)-13*k -32 = 7*4^(k+1)-13*(k+1)-19$
Tímto jsme dokázali hypotézu
Pro n=>n0 platí $f(n)=7*4^n-13*n-19$ za předpokladu, že $n=>152$
pro n=152 $-13*n-32<=-2009$ $-2009<=-2009$

Kondr · 17. 11. 2009 16:24 — Editoval Kondr (17. 11. 2009 16:25)

↑ sealer:Možná ten konec přeformulovat, aby bylo jasné, že hypotéza platí a že vyhovujícím n_0 je např. 152.

FigeraldKenedy · 17. 11. 2009 17:14

sealer: Můžu se zeptat jak jsme došli k tomu n=>152?

f(n)<=7*4^n-13*n-19 k tomuto sjme nějak došli enbo jsme to dostali zadané děkuji

sealer · 17. 11. 2009 18:34 — Editoval sealer (17. 11. 2009 18:47)

↑ FigeraldKenedy:
To 152 jsem si osobně dopočítal tím, že jsem dosazoval čísla taková, dokud mě něvyšla rovnost $-13*n-32<=-2009$

k tomu druhému dotazu, bylo to zde zmíněno i jiného topicu...Odkaz

JouiBart · 17. 11. 2009 20:25

↑ Kondr: Aaa díky už chápu, vyškrtal jsi z obou stran to $4*3^n$ ...

FigeraldKenedy · 17. 11. 2009 21:53

Zdravím, postupoval jsem podle příspěvků co jsou tady na foru a snažil se to vypočítat ale podle mě jsem nedošel k výsledku. vím že nejsem u konce ale ted ten "mezivýsledek" se mi nelíbí. Napadlo mě zesílit indukční krok ale za prvé nejsem si moc jistý jak se to dělá a jestli by to vůebc pomohlo a nebo to mám uplně celé špatně, díky:-)

Řešte následující (jediný) příklad:
Je dána funkce f(n) z přirozených do celých čísel tímto rekurentním předpisem:
f(0) = −10
f(n + 1) = 4 · f(n) + 36 · n + 42 pro všechna n ¸ 0
Vašim úkolem je dokázat následující matematickou větu (o naší dané f).
Existuje přirozené n0 takové, že pro všechna n ¸ n0 platí
f(n) · 8 · 4n − 2009

přes tuto stránku jsem si vypočítal hypotezu (nevím jetsli jsem to pojmenoval dobře)
http://www.wolframalpha.com/input/?i=f% … 0%29%3D-10

Báze indukce:
f(0)=-10
f(n)=2*(-6*n+2^(2*n+2) -9)
dosadím za n=0 a zjistím že -10=-10 ….-> L=P

indukční krok:

f(k)=2*(-6*k+2^(2*k+2) -9)

f(k+1)=2*(-6*(k+1)+2^(2*(k+1)+2) -9)
mylsím že se tomuto říká zesílední indukčního kroku

ted dosadím do f(n + 1) = 4 · f(n) + 36 · n + 42

f(n + 1) = 4 * (2*(-6*(k+1)+2^(2*(k+1)+2) -9)) + 36 * n + 42=

=-48*k+2^(2*(k+1)+5) -72+36*k+42= /**roznásobil jsem závorky a tu 8 jsem dal 2 „na“3
=-12*k+2^(2*(k+1)+5)-30=
=2*(-6*k +2^(2*(k+1)+4) -15)=
=2*(-6*(k+1)+2^(2*(k+1)+4)-9)

Matematické Fórum

#1 11. 11. 2009 19:51

Matematický důkaz

Code:

#2 11. 11. 2009 21:06

Re: Matematický důkaz

#3 11. 11. 2009 22:01

Re: Matematický důkaz

#4 11. 11. 2009 22:16 — Editoval JouiBart (11. 11. 2009 22:18)

Re: Matematický důkaz

Code:

#5 11. 11. 2009 22:20

Re: Matematický důkaz

#6 15. 11. 2009 13:13 — Editoval JouiBart (15. 11. 2009 13:13)

Re: Matematický důkaz

Code:

#7 15. 11. 2009 21:34 — Editoval Blizzy (15. 11. 2009 21:49)

Re: Matematický důkaz

#8 16. 11. 2009 11:07 — Editoval JouiBart (16. 11. 2009 11:52)

Re: Matematický důkaz

#9 16. 11. 2009 11:22

Re: Matematický důkaz

#10 16. 11. 2009 11:40

Re: Matematický důkaz

#11 16. 11. 2009 11:58

Re: Matematický důkaz

#12 16. 11. 2009 12:07

Re: Matematický důkaz

#13 16. 11. 2009 12:37

Re: Matematický důkaz

#14 16. 11. 2009 12:39

Re: Matematický důkaz

#15 17. 11. 2009 11:38

Re: Matematický důkaz

#16 17. 11. 2009 16:12

Re: Matematický důkaz

#17 17. 11. 2009 16:24 — Editoval Kondr (17. 11. 2009 16:25)

Re: Matematický důkaz

#18 17. 11. 2009 17:14

Re: Matematický důkaz

#19 17. 11. 2009 18:34 — Editoval sealer (17. 11. 2009 18:47)

Re: Matematický důkaz

#20 17. 11. 2009 20:25

Re: Matematický důkaz

#21 17. 11. 2009 21:53

Re: Matematický důkaz

Zápatí