Rekursive Gleichungen lösen

[win8789]

Hallo,
ich würde gerne wissen, wie man bei der Lösung rekursiver Gleichungen vorgeht.
Beispiel: C[N] = C[N-1] + N für N >= 2, mit C[1] = 1.

Augelöst = C[N] beträt ungefähr N²/2

Im Buch steht dazu folgende Rechnung (von mir kommentiert):

C[N] = C[N-1] + N

= C[N-2] + (N-1) + N // das N-1 kommt doch daher, dass das N aus C[N-1] = N -1 sein muss und dann nur noch das C[N-2] aus C[N-1] zurück bleibt, oder?

= C[N-3] + (N-2) + (N-1) + N

...

= C[1] + 2 + ....+ (N-2) + (N-1) + N

= 1 + 2 + ... + (N-2) + (N-1) + N //soweit verstehe ich es, glaube ich zumindest

= (N(N+1)/2 //wie jetzt das?

bei der Erklärung steht nun, das man N * (N+1) und dies doppelt so groß ist wie das Ergebnis also noch geteilt durch 2.
Wie kommt man nun auf das geteilt durch 2?
Meine Idee: Man läuft die Rechnung N mal durch und die "Grundstellung" ist C[2] = 1 + N oder N+1 also N(N+1), aber wie geht man dann weiter vor um das geteilt durch 2 zu erhalten?

Ein anderes Beispiel:

C[N] = C[N/2] + N, für N >=2, mit C[1] = 0
C[N] = ungefähr 2N //steht so im Buch

Meine Überlegungen: Man läuft die Gleichung log2(N) durch (wenn N eine zweierpotzen ist) und hat als Grundformel C[2] = 0 + N. Müsste das Ergebnis dann nicht log2(N)*N sein? Wie kommt man also auf das Ergebnis.

Ich gebe zu bedenken, dass ich das Thema Rekursion noch nicht in der Schule hatte (glaube auch nicht, dass ich es in der Oberstufe haben werde). Für eine einfache und ausführliche Antwort wäre ich also sehr dankbar, oder für Lehrmaterial, welches das Thema recht einfach erklärt.

für Hilfe wäre ich sehr dankbar.

p.s Das O bei der O-Notation glit doch immer für den größten N-Wert einer Rechnung, wenn g(n) = O(g(n)) gelten soll?
Beispiel: g(n) = n² +n; g(n) = O(n²)
oder g(n) = n*lg(n) +n; g(n) = O(n) (für zumindest kleinere Werte für n, da irgendwann n*lg(n) größer ist)

[cloidnerux]

ich würde gerne wissen, wie man bei der Lösung rekursiver Gleichungen vorgeht.
Beispiel: C[N] = C[N-1] + N für N >= 2, mit C[1] = 1.

Es gibt wohl keine allgemeine Vorgehensweise bei Rekursion. Hier in deinem Fall musst du die Rekursion in eine Summe umwandeln, sodass du es analytisch betrachten kannst.

Dein erstes beispiel ist die Summe aller natürlichen Zahlen von 1 bis N, dies lässt sich über die Formel (N*(N+1))/2 beschreiben, diese wird Gaussche Summenformel genannt https://de.wikipedia.org/wiki/Gau%C3%9F ... mmenformel

Dein zweites Beispiel ist die Summe aller Zahlen N/(2^k) mit (N/(2^k)) > 1, wenn du dies aufschreibst siehst du, dass du

Code: Alles auswählen

N * sum 1/(2^k) k=1 to K

hast. Mit K => unendlich ist diese Summe 2(gibt es beweise zu), damit ist die Rekursion C(N) = N + C(N/2) für hinreichend große N gleich 2*N

Das O bei der O-Notation glit doch immer für den größten N-Wert einer Rechnung

Ich kenne mich nicht mit der groß-O Notation aus, aber an sich soll es das Verhalten bei großen n beschreiben. Bei einem verhalten n^2+n wird für große n der Summand n^2 dominieren.
Hättest du z.B e^n + n^10 würde für ein hinreichend großes n der Term e^n dominieren.

[Xin]

C[N] = C[N-1] + N

= C[N-2] + (N-1) + N // das N-1 kommt doch daher, dass das N aus C[N-1] = N -1 sein muss und dann nur noch das C[N-2] aus C[N-1] zurück bleibt, oder?

= C[N-3] + (N-2) + (N-1) + N

= C[1] + 2 + ....+ (N-2) + (N-1) + N

= 1 + 2 + ... + (N-2) + (N-1) + N //soweit verstehe ich es, glaube ich zumindest

Soweit so gut. (Kommentar ist korrekt)

Wenn N Element aus der Menge der natürlichen Zahlen.
Ist C[1] als 1 definiert?

= (N(N+1)/2 //wie jetzt das?

Was passiert hier? Guck Dir einen Würfel an: Ein Würfel mit einer Seite (C[1]) hat insgesamt 1 Auge. Ein Würfel mit 2 Seiten hat soviele Augen, wie ein Würfel mit 1 Seite + 2. Würfel[6] = Würfel[5] + 6. Nehmen wir also einen Würfel mit 6 Seiten. C[6] = 6+5+4+3+2+1 = 21, genau wie 6*7/2.
Warum also 6*7/2. Wir haben 6 Seiten. Die Augenzahl der gegenüberliegenden Seiten ist 7 (also 6+1, 5+2, 4+3), das entspricht N+1.
Da wir aber immer zwei Seiten gleichzeitig betrachten, haben wir in der Gesamtbetrachtung nur noch 6/2 Doppelseiten, die jeweils 7 Augen haben: (N/2)(N+1). Anders geschrieben N(N+1)/2.

C[N] = C[N/2] + N, für N >=2, mit C[1] = 0
C[N] = ungefähr 2N //steht so im Buch

Meine Überlegungen: Man läuft die Gleichung log2(N) durch (wenn N eine zweierpotzen ist) und hat als Grundformel C[2] = 0 + N. Müsste das Ergebnis dann nicht log2(N)*N sein? Wie kommt man also auf das Ergebnis.

Das entspricht ja einer Reihenentwicklung, wobei mich interessiert, wie C[3] auszusehen hat, ich gehe mal davon aus, dass C[N]=0 bei N<2, so dass C[3] = 3?

Nehmen wir eine einfache Zahl C[8] = 8 + 4 + 2 + C[1] = = 8 + 4 + 2 + 0 = 14.
Unter der Bedingung, dass N == 2^m entspricht, dann ist C[N] die Summe von i=0 bis m über 2^i, was (2^(m+1)-1)-1 (letztes -1 weil C[1] == 0) entspricht.
Bei N==8 bedeutet das 8 = 2^3, also m==3. C[N] = 2^4-2 = 14, was ungefähr 2 * N entspricht.

Wenn man sich die Zahl binär anguckt 8 = 1000, dann schaltet diese Rechnung die nachfolgenden Bits ein: 14 = 1110, womit sich die Zahl fast verdoppelt. Die Rekusion nimmt sich Bit für Bit vor, bis wir beim Rekursionsanker ankommen (C[1]=0). Da der Rekursionsanker eigentlich recht früh greift bleibt das letzte Bit 0.

Nehmen wir uns das ganze für C[6] vor, das ist 6+3+0 == 9, was ungefähr 2*6 ist. Der Fehleranteil liegt bei 25%.
Bei C[8] war der Fehleranteil 12,5%. C[10] ist 10+5+2,5+0= 17,5 (12,5%), C[30] = 30+15+7,5+3,25+0 = 55,75 (9,3%).
Nehmen wir noch was größeres C[100] = 100+50+25+12,5+6,25+3,125 = 196,875 (1,6% Fehlerquote).
Wir nähern uns also der 2N immer weiter an. Eine Verdopplung erreichen wir unter optimalen Bedingungen nicht, außerdem ist C[N<2] = 0, womit wir nichtmals optimale Bedingungen haben.

p.s Das O bei der O-Notation glit doch immer für den größten N-Wert einer Rechnung, wenn g(n) = O(g(n)) gelten soll?
Beispiel: g(n) = n² +n; g(n) = O(n²)
oder g(n) = n*lg(n) +n; g(n) = O(n) (für zumindest kleinere Werte für n, da irgendwann n*lg(n) größer ist)

Nehmen wir an, dass n im Regelfall über >=4 ist