Rekusrionsgleichung - wie lösen?

P(n) = 1/n * Summe von k=0 bis n-1 ( P(k) + P(n - k - 1) + n - 1 )

Wie kann ich das auflösen?

Michael E.

Der Ausdruck ist gar nicht definiert, denn für jedes n wird P(k) mit k = 0 ausgewertet. Aber 1/k mit k = 0 ist nicht definiert.

Hmm, da steht noch etwas:

Machen sie geeignete Annahmen über den Rekursionsanker.
Sieht so aus, als ob ich P(0) selbst definieren müsste.

Aber wie gehen ich dann vor? Eine Rekursionsgleichung mit einer Summe innen hab ich noch nie gesehen

Michael E.

Die Summe wirst du schnell los, wenn du P(n) durch P(n-1) ausdrückst.

Spoiler: http://ideone.com/zscy2

Ich würde mal ausrechnen, was n*p(n)-(n-1)*p(n-1) ist.

ich komm leider auf ein ergebnis: mein versuch das ganze mit nem cas zu lösen hat auch nur das ergeben:

$\left( 2\,n+2 \right) \Psi \left( n \right) +2\,{\frac {-2\,{n}^{2}+n +\gamma\,n+1+\gamma\,{n}^{2}}{n}}$

\left( 2\,n+2 \right) \Psi \left( n \right) +2\,{\frac {-2\,{n}^{2}+n
+\gamma\,n+1+\gamma\,{n}^{2}}{n}}

Irgendwelche Psi-Terme drin, die mir nichts sagen, wie ist denn die lösung? Vlt komm ich dann selbst drauf

Michael E.

Ich bin wahnsinnig schlecht darin, Rekursionen aufzulösen. Deshalb gibts bestimmt ne deutlich einfachere Lösung.

Sei P(0) := t. Dann ist P(n) = (n+1)t + 2*summe{i=3 bis n+1} ((n+1)/i - (n+1)/(i²-i)) = (n+1)t + 2*summe{i=3 bis n+1} (n+1)/i * (i-2)/(i-1).

Michael E.

Mit Wolframalpha vin ich noch auf P(n) = (n+1)(t + 2H_n) - 4n gekommen, wobei H_n die harmonische Summe ist.

@Michael:
In deinem "spoiler" hast du doch ein ganz wunderbares Ergebnis gepostet. Warum fängst du jetzt mit komischen wolfram-Lösungen an?!

@shisha:

Folge doch mal meinem Tipp von oben und rechne aus, was
n*p(n) - (n-1)*p(n-1)
ist.

Vorher vielleicht die Summe ein bisschen vereinfachen (konstanten Term rausziehen, p(k) und p(n-k-1)in zwei eigene Summen schreiben und nochmal ganz genau anschauen), dann kannst du einfacher rechnen.

Dann bekommst du eine summenfreie Gleichung n*p(n) - (n-1)*p(n-1) = irgendwas. Die dann einfach nach p(n) auflösen.

@Michael: Sorry, habe falsch gelesen. Es geht ja nicht nur um summenfrei, sondern auch um rekursionsfrei. Dann meinen letzten post nicht zu ernst nehmen: Damit kommt man nur zu einer summenfreien Rekursion.

Weiter oben sind wir ja schonmal auf

p(n) = (n+1)/n * p(n-1) + 2*n-1

gekommen.

Mit wiederholtem Einsetzen kommt man z.b. auf

p(5) =

6/5 * ( 5/4 * ( 4/3 * ( 3/2 * ( 2/1 p0 + 2*0 ) + 2*1/2 ) + 2*2/3 ) + 2*3/4 ) + 2 * 4/5

= (6/5 * 5/4 * 4/3 * 3/2 * 2/1) p0 
+ (2*1/2) * 4/3 * 5/4 * 6/5
+ (2*2/3) *       5/4 * 6/5
+ (2*3/4) *             6/5
+ (2*4/5)

Jetzt scharf hinsehen und alle Brüche kürzen, dann ist das

= 6*p0 + 2*1/2*6/3 + 2*2/3*6/4 + 2*3/4*6/5 + 2*4/5*6/6
= 6*p0 + 2*6*(1/2/3 + 2/3/4 + 4/5/6)

Verallgemeinern und hoffen das es stimmt:

p(n) = (n+1)* (p0 + summe (k=1...n-1)  k/(k+1)/(k+2))

Induktionsanfang: p(0) = 1*p0 + 0 --> klappt
Induktionsschulss:

p(n+1) = (n+2)/(n+1) * (n+1)[p0 + summe (k=1...n-1)  k/(k+1)/(k+2) ] + 2 * n/(n+1)
       = (n+2) [p0 + summe (k=1...n-1)  k/(k+1)/(k+2) ] + 2 * n/(n+1) * (n+2)/(n+2)
      = (n+2) [p0 + summe (k=1...n-1)  k/(k+1)/(k+2) + 2 * n/(n+1)/(n+2)]
      = (n+2) [p0 + summe (k=1...n)  k/(k+1)/(k+2) ]

Klappt auch

Das sieht ganz anders aus als eure CAS-Lösungen, ist aber vermutlich das selbe.

Michael E.

Mups schrieb:

Das sieht ganz anders aus als eure CAS-Lösungen, ist aber vermutlich das selbe.

Ist genau dasselbe wie meine Lösung. Die hab ich übrigens auch von Hand erstellt. Lediglich die Umformung der Summe in die harmonische Reihe hab ich Wolframalpha machen lassen.