Abschätzung Rekurrenz

18/06/2009 - 13:05 von Oliver Friedmann | Report spam
Hallo!

Ich suche nach einer (möglichst guten) unteren Schranke an folgende
Rekurrenz:

f(0) = 1
f(n) = f(n-1) + (1/n) * h(n-1)

h(0) = 1
h(n) = f(n) + h(n-1)

Man kann das natürlich auch ohne h(n) schreiben, dann eben mit einer
endlichen Summe:

f(0) = 1
f(n) = f(n-1) + (1/n) * (\sum_{i=0}^{n-1} f(i))

Die untere Schranke sollte (= möchte ich und vermute ich ;-) )
superpolynomiell sein; ich vermute, dass sie in der Region 2^sqrt(n)
bzw. 2^sqrt(n*log n) liegt.

Möglicherweise kann man das leicht abschàtzen, ich sehe aber nicht wie,
vielleicht ist meine Vermutung auch falsch - bin allerdings auch kein
Experte auf diesem Gebiet.

Vielen Dank,
Oliver
 

Lesen sie die antworten

#1 Stephan Gerlach
18/06/2009 - 14:55 | Warnen spam
Oliver Friedmann schrieb:

Ich suche nach einer (möglichst guten) unteren Schranke an folgende
Rekurrenz:

f(0) = 1
f(n) = f(n-1) + (1/n) * h(n-1)

h(0) = 1
h(n) = f(n) + h(n-1)

Man kann das natürlich auch ohne h(n) schreiben, dann eben mit einer
endlichen Summe:

f(0) = 1
f(n) = f(n-1) + (1/n) * (\sum_{i=0}^{n-1} f(i))



Da die Folge monoton wachsend ist, ist eine "möglichst gute" untere
Schranke der Folge 1?!
Das war aber bestimmt nicht gemeint.

Die untere Schranke sollte (= möchte ich und vermute ich ;-) )
superpolynomiell sein; ich vermute, dass sie in der Region 2^sqrt(n)
bzw. 2^sqrt(n*log n) liegt.



Das klingt eher so, als wolltest du eine asymptotische Nàherung für
deine Folge?! Also so was in der Art, wie man n! für große n durch die
Stirling-Formel annàhern kann.

Die ersten 6 Folgenglieder deiner Folge lauten
f(0) = 1/1
f(1) = 2/1
f(2) = 7/2
f(3) = 34/6
f(4) = 209/24
f(5) = 1546/120.
Der Nenner ist jeweils gerade n!. Beim Zàhler hilft dir vielleicht
irgendwie das hier
<http://www.research.att.com/~njas/sequences/?q=2%2C7%2C34%2C209%2C1546&sort=0&fmt=0&language=english&go=Search>
weiter.


Eigentlich sollte Brain 1.0 laufen.


gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)

Ähnliche fragen