Rekursionsgleichung lösen

27.04.2012, 20:03

Oromis

Rekursionsgleichung lösen

Hallo liebe Matheexperten,

ich studiere im 2. Semester Informatik. In der neuesten Übung unserer Algorithmen & Datenstrukturen-Vorlesung ist folgende Aufgabe aufgetaucht:

Lösen Sie die folgenden Rekursionsgleichungen exakt:

$\begin{eqnarray*} S(1) = 1, S(n) = \sum_{i=1}^{n-1} i \cdot S(i)\quad f\ddot ur\, n > 1 \end{eqnarray*}$

Leider haben wir Rekursionsgleichungen noch nie behandelt, also habe ich mich im Internet selber dazu schlau gemacht und auch die ersten 3 (Hier nicht dargestellten) Aufgaben gelöst & verstanden. Nur diese hier bereitet mir Kopfschmerzen.

Per Brute-Force (nachprogrammieren und ausgeben lassen) habe ich dann auch die Lösung gefunden:

$\begin{eqnarray*} S(n) = \frac{n!}{2}\quad f\ddot ur\ alle\ n \geq 1 \end{eqnarray*}$

Leider habe ich keinen Schimmer, wie ich ohne Computerunterstützung darauf kommen könnte ...

Vielen Dank für alle Denkunterstützungen Augenzwinkern

mfg

Oromis

27.04.2012, 20:16

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Oromis
Per Brute-Force (nachprogrammieren und ausgeben lassen) habe ich dann auch die Lösung gefunden:

$\begin{eqnarray*} S(n) = \frac{n!}{2}\quad f\ddot ur\ alle\ n \geq 1 \end{eqnarray*}$

Leider habe ich keinen Schimmer, wie ich ohne Computerunterstützung darauf kommen könnte ...

Es ist doch völlig in Ordnung und legitim, dass man Behauptungen nach umfangreicher Untersuchung von Beispielen aufstellt. Freude

Nur der Beweis, dass diese Behauptung dann auch für alle $\begin{eqnarray*} n \end{eqnarray*}$ stimmt, sollte exakt mathematisch durchgeführt werden - im vorliegenden Fall ist das per Vollständiger Induktion (mit Start n=2) relativ einfach möglich.

27.04.2012, 21:14

Oromis

Auf diesen Beitrag antworten »

Ersmal Danke für deine Antwort Freude

Ach ja, die leidige Induktion ....

Induktionsanfang hat ja gut geklappt, aber für den Induktionsschritt fällt mir nichts mehr ein:

$\begin{eqnarray*} \sum_{i=1}^{n}i \cdot S(i) = \frac{(n+1)!}{2}\\<br /> \sum_{i=1}^{n-1}i \cdot S(i) + n \cdot S(n) = \frac{n! \cdot (n+1)}{2} \end{eqnarray*}$

Und jetzt? Auf der linken Seite S(n) ersetzen? Oder die Summe? Oder beides? Hat mich alles nicht wirklich weitergebracht ...

27.04.2012, 21:22

HAL 9000

Auf diesen Beitrag antworten »

Leider frönst du auch der Unsitte, nicht sauber und klar und deutlich zu sagen, was in deinem Induktionsschritt noch Behauptung ist und was du schon nachgewiesen hast ...

Egal: Für $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ kann man (ganz ohne Induktion) auf der Basis der gegebenen Rekursionsgleichung folgern

$\begin{eqnarray*} S(n+1) = \sum_{i=1}^{n} iS(i) = \sum_{i=1}^{n-1} iS(i) + nS(n) = S(n)+nS(n) = (n+1)S(n) \end{eqnarray*}$ ,

was man im Induktionsschritt dann verwenden kann.

27.04.2012, 21:43

Oromis

Auf diesen Beitrag antworten »

Argh, so kurz vor dem Ziel versagt, das hatte ich schon fast dastehen Hammer

Zitat:

Original von HAL 9000
Leider frönst du auch der Unsitte, nicht sauber und klar und deutlich zu sagen, was in deinem Induktionsschritt noch Behauptung ist und was du schon nachgewiesen hast ...

Ähhhhm, sorry? Ich weiß leider grade nicht, was du damit meinst...

Hätte ich folgendes noch anfügen sollen?

$\begin{eqnarray*} S(n) = \sum_{i=1}^{n-1} iS(i)\; (Direkt\ aus\ der\ Gleichung) \end{eqnarray*}$
Induktionsanfang:
$\begin{eqnarray*} \sum_{i=1}^{2-1}iS(i) = 1 \\<br /> \frac{2!}{2} = 1\\<br /> \end{eqnarray*}$
=> Gezeigt für n = 2. Im Induktionsschritt kann ich nun $\begin{eqnarray*} \sum_{i=1}^{n-1} iS(i) = \frac{n!}{2} \end{eqnarray*}$ verwenden.

Anyway, vielen Dank für deine Hilfe!

27.04.2012, 21:49

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Oromis
Ähhhhm, sorry? Ich weiß leider grade nicht, was du damit meinst...

Es ist dieselbe leidige Diskussion wie hier

Formalismus bei der vollständigen Induktion ,

ich möchte sie nicht immer und immer wieder führen müssen. unglücklich

30.04.2012, 15:32

Mystic

Auf diesen Beitrag antworten »

Wobei es hier auch Beweisalternativen gibt, welche den Vorteil haben, dass man besser "sieht", wie es zu dieser Formel kommt... Was nämlich bei genauerer Betrachtung dahinter steckt, ist nichts anderes als die Teleskopformel

$\begin{eqnarray*} n!-1= \sum_{k=0}^{n-1} \underbrace{kk!}_{(k+1)!-k!} \end{eqnarray*}$

wobei man die Summanden kombinatorisch deuten kann als diejenigen Permutationen auf {1,2,...,n}, welche schon k+2,k+3,..,n als Fixpunkt haben und für die k+1 nicht auch Fixpunkt ist, was insgesamt also auf die "Klassengleichung" einer Partition von $\begin{eqnarray*} S_n \setminus \{id\} \end{eqnarray*}$ hinausläuft...

01.05.2012, 13:24

HAL 9000

Auf diesen Beitrag antworten »

Es gibt natürlich immer Alternativen, aber wieso man aufgrund von $\begin{eqnarray*} n!-1= \sum_{k=0}^{n-1} \underbrace{kk!}_{(k+1)!-k!} \end{eqnarray*}$ "sehen" soll, dass $\begin{eqnarray*} S(n) = \frac{n!}{2} \end{eqnarray*}$ (insbesondere das $\begin{eqnarray*} \frac{1}{2} \end{eqnarray*}$ ) gilt, bedarf schon eines sehr weitreichenden Blickes. Augenzwinkern

01.05.2012, 15:33

Mystic

Auf diesen Beitrag antworten »

Naja, so "weitreichend" nun auch wieder nicht, denn immerhin folgt ja aus obiger Gleichung, indem durch 2 dividiert, sofort

$\begin{eqnarray*} \frac{n!}2= 1(\frac {1!}2+\frac 12)+ \sum_{k=2}^{n-1} k\frac{k!}2 \end{eqnarray*}$

Definiert man somit eine Funktion S(n) auf $\begin{eqnarray*} \mathbb{N}^* \end{eqnarray*}$ , welche sich von n!/2 nur an der Stelle n=1 unterscheidet, indem sie dort den Wert 1 annimmt, so ist man genau bei der Funktion, um die es hier geht... Augenzwinkern

Neue Frage »

Antworten »

Rekursionsgleichung lösen

Verwandte Themen