Rekursionsgleichung lösen

Neue Frage »

Oromis Auf diesen Beitrag antworten »
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:



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:



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

Vielen Dank für alle Denkunterstützungen Augenzwinkern

mfg

Oromis
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:



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 stimmt, sollte exakt mathematisch durchgeführt werden - im vorliegenden Fall ist das per Vollständiger Induktion (mit Start n=2) relativ einfach möglich.
 
 
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:



Und jetzt? Auf der linken Seite S(n) ersetzen? Oder die Summe? Oder beides? Hat mich alles nicht wirklich weitergebracht ...
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 kann man (ganz ohne Induktion) auf der Basis der gegebenen Rekursionsgleichung folgern

,

was man im Induktionsschritt dann verwenden kann.
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?


Induktionsanfang:

=> Gezeigt für n = 2. Im Induktionsschritt kann ich nun verwenden.

Anyway, vielen Dank für deine Hilfe!
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
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



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 hinausläuft...
HAL 9000 Auf diesen Beitrag antworten »

Es gibt natürlich immer Alternativen, aber wieso man aufgrund von "sehen" soll, dass (insbesondere das ) gilt, bedarf schon eines sehr weitreichenden Blickes. Augenzwinkern
Mystic Auf diesen Beitrag antworten »

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



Definiert man somit eine Funktion S(n) auf , 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 »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »