Doppelpost! Rekursionsgleichung mit enthaltener Summe

19.10.2013, 16:44

litaspike

Rekursionsgleichung mit enthaltener Summe

Meine Frage:
Hallo Mathematiker!

(Ich bin mir leider mit dem Thema nicht so sicher, deswegen hier..)

Ich habe eine zu bearbeitende Aufgabe, auf deren Lösung ich einfach nicht komme. Ich hoffe, ihr könnt meine Lösungsansätze überprüfen und korrigieren.

Es geht um folgendes

$\begin{eqnarray*} S(1) = 1, S(n) = \sum\limits_{i=1}^{n-1} i * S(i); n \geq 2 \end{eqnarray*}$

Ich möchte gerne diese Rekursionsgleichung lösen, und diese im Anschluss mit Induktion beweisen.

Meine Ideen:
Mein Ansatz war nun:

Um die Summe zu eliminieren, nehme ich

$\begin{eqnarray*} S(n) - S(n-1) \end{eqnarray*}$

Als Ergebnis bekomme ich hier aber

$\begin{eqnarray*} S(n) = n * S(n-1) \end{eqnarray*}$

Müsste ich nun nicht diese Gleichung nach dem altbekannten Schema auflösen und erhalte dann das Ergebnis?
Bei mir kommt aber leider nicht die richtige Lösung heraus.

Liegt es an der Vorgehensweise?

19.10.2013, 17:53

jimmyt

Auf diesen Beitrag antworten »

RE: Rekursionsgleichung mit enthaltener Summe

Zitat:

Original von litaspike
...
Es geht um folgendes

$\begin{eqnarray*} S(1) = 1, S(n) = \sum\limits_{i=1}^{n-1} i * S(i); n \geq 2 \end{eqnarray*}$

Ich möchte gerne diese Rekursionsgleichung lösen, und diese im Anschluss mit Induktion beweisen.

Meine Ideen:
...
Als Ergebnis bekomme ich hier aber

$\begin{eqnarray*} S(n) = n * S(n-1) \end{eqnarray*}$

...

Interessante Aufgabe.
Ich bin auf dasgleiche Ergebnis wie du gekommen, für $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$ .
Also:

$\begin{eqnarray*} S(1) = 1 ; \quad S(2) = 1; \quad S(n) = n \cdot S(n-1) \end{eqnarray*}$

Allerdings klappt bei mir die vollständige Induktion noch nicht. I.V. ist klar, I.A. klappt auch, aber am I.S. hapert es noch.
Ich habe als Zwischenergebnis $\begin{eqnarray*} n \cdot (S(n) + S(n-1)) \end{eqnarray*}$ raus. Hast du das auch?
Daraus muss $\begin{eqnarray*} (n+1) \cdot S(n) \end{eqnarray*}$ gemacht werden. Vlt. ist es auch offensichtlich, nur ich sehe es grad nicht. Augenzwinkern

19.10.2013, 19:23

litaspike

Auf diesen Beitrag antworten »

Antwort
Hei jimmyt smile

Danke für deine Hilfe!

Bei der Induktion bin ich leider noch gar nicht, weil ich mir mit meiner Lösung nicht so ganz sicher bin.

So weit ich Rekursionsgleichungen verstanden habe müsste ich nun S(n) = n * S(n-1) lösen.

Lösung wäre

$\begin{eqnarray*} x(x+1) / 2 \end{eqnarray*}$

Gebe ich hier allerdings x = 3 ein, dann erhalte ich als Ergebnis 6.

Lösung von S(3) ist aber 3.

Da kann doch etwas nicht stimmen? Sehe ich den Wald vor lauter Bäumen nicht?

Grüße, lana

19.10.2013, 19:47

litaspike

Auf diesen Beitrag antworten »

Antwort
Wenn ich die Induktion über $\begin{eqnarray*} \sum\limits_{i=1}^{n-1} i * S(i) = n * S(n-1) \end{eqnarray*}$ führe, dann sieht sie so aus:

I.A. n = 2
S(2) = 1 * S(1) = 1 * 1 = 1
$\begin{eqnarray*} S(2) = \sum\limits_{i=1}^{1} i * S(i) = 1 * S(1) = 1 * 1 = 1 \end{eqnarray*}$

I.V. für ein beliebiges, aber festes n gilt $\begin{eqnarray*} \sum\limits_{i=1}^{n-1} i * S(i) = n * S(n-1) \end{eqnarray*}$

I.S. n = n+1
$\begin{eqnarray*} S(n+1) = \sum\limits_{i=1}^{n+1} i * S(i) = n * S(n-1) + (n+1) * S(n+1) = n * S(n-1) + n * S(n+1) + S(n+1) =??? \end{eqnarray*}$
$\begin{eqnarray*} n * S(n-1) + n * S(n) = S(n) + n * S(n) = (n+1) * S(n) \end{eqnarray*}$

Ich komme noch nicht ganz auf die mit '???' markierte Stelle, hättest du einen Tipp?

Vielen Dank schon mal, du hast mir sehr geholfen, falls es so wirklich ausreicht smile

Grüße, lana

19.10.2013, 20:48

alterHund

Auf diesen Beitrag antworten »

Doppelpost
http://matheplanet.com/matheplanet/nuke/...post_id=1379981

19.10.2013, 22:50

litaspike

Auf diesen Beitrag antworten »

Antwort
Puh, okay.

Durch Ausprobieren ist die Lösung der Gleichung nun auf jeden Fall als diese hier erkannt worden:

$\begin{eqnarray*} n!/2 \end{eqnarray*}$

Stichproben geben mir Recht. Liege ich denn diesmal richtig?

Nun hapert es nur noch am Beweis.
Die Induktion oben ist Murks, ich habe mich mit der Ursprungssumme geirrt. Neue Versuche ergeben leider auch kein zufrieden stellendes Ergebnis.

Ich höre für heute auf, mal sehen ob mir morgen etwas einfällt.

Gute Nacht und vielen Dank euch!

19.10.2013, 23:21

litaspike

Auf diesen Beitrag antworten »

Antwort
Ach, natürlich:

$\begin{eqnarray*} I.A. n= 0 \sum\limits_{i=1}^{1} n*S(n) = 1 * S(1) = 1 \frac{2!}{2} = 1 I.V. \sum\limits_{i=1}^{n-1} i*S(i) = \frac{n!}{2} I.S. n = n+1 \sum\limits_{i=1}^n i*S(n) = \sum\limits_{i=1}^{n-1} i*S(i) + n*S(n) = \frac{n!}{2} + n*S(n) = \frac{n!}{2} + n * \frac{n!}{2} = (n+1) \frac{n!}{2} = \frac{(n+1)!}{2} \end{eqnarray*}$

Manchmal brauche ich einfach etwas länger. :P

20.10.2013, 10:35

HAL 9000

Auf diesen Beitrag antworten »

Im Grunde genommen in Ordnung, zwei kleine Fehler bzw. Formverstöße:

Zitat:

Original von litaspike
$\begin{eqnarray*} I.A. n= 0 \end{eqnarray*}$

Der Induktionsanfang ist hier nicht $\begin{eqnarray*} n=0 \end{eqnarray*}$ , sondern $\begin{eqnarray*} n=2 \end{eqnarray*}$ , und so hast du ja auch im folgenden gerechnet.

Zitat:

Original von litaspike
$\begin{eqnarray*} I.S. n = n+1 \end{eqnarray*}$

Hier meinst du wohl $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ .

20.10.2013, 10:46

jimmyt

Auf diesen Beitrag antworten »

RE: Antwort
Zur vollständigen Induktion hat HAL 9000 schon alles gesagt. Die ist abgesehen von den 2 Sachen ok.
Aber mal ne Frage:
Wie bist du darauf

Zitat:

Original von litaspike
...
$\begin{eqnarray*} n!/2 \end{eqnarray*}$
...

gekommen?
Die stimmt, keine Frage. Mich interessiert aber, wie du drauf gekommen bist. Einfach probieren, raten?

20.10.2013, 11:41

litaspike

Auf diesen Beitrag antworten »

Antwort
Da hast du natürlich Recht, Hal9000 smile

jimmyt, ich habe einfach nur stupide gerechnet und ausprobiert:

S(n) = n * (n-1) * (n-2) * ... * 3 * 1 * 1

Das ist die Fakultät ohne die 2. Also n! und durch 2 teilen.

Da ich das Ergebnis im Anschluss sowieso beweisen muss, ist das wohl legitim?

Vielen Dank, jimmyt, vielen Dank Hal9000, ihr habt mir sehr geholfen.

20.10.2013, 13:37

jimmyt

Auf diesen Beitrag antworten »

Ahh ^^ stimmt. Augenzwinkern

Da hätte ich auch drauf kommen können.

$\begin{eqnarray*} S(n)=n \cdot S(n-1) \stackrel{\text{Def. von S(n-1)}}{=} n \cdot (n-1) \cdot S(n-2) = \dots \end{eqnarray*}$

$\begin{eqnarray*} = n \cdot (n-1) \dots \cdot 3 \cdot S(2) \stackrel{\text{Def. von S(2)}}{=} n \cdot (n-1) \dots \cdot 3 \cdot 1 \end{eqnarray*}$

$\begin{eqnarray*} \stackrel{\text{erweitern mit 2}}{=}\frac{n \cdot (n-1) \dots \cdot 3 \cdot 2 \cdot 1}{2} = \frac{n!}{2} \end{eqnarray*}$

Coole Aufgabe. Und gerne geschehen, jederzeit wieder.

20.10.2013, 19:14

sulo

Auf diesen Beitrag antworten »

Zitat:

Original von jimmyt
Und gerne geschehen, jederzeit wieder.

Nein, eher nicht.
Der Fragesteller hat Crossposting betrieben, und das wird normalerweise mit einem Schließen des Threads geahndet.

Leider hat niemand auf die Mahnung von alterHund geachtet und es wurde trotz Crossposting weiter geholfen. Zum Schließen ist es jetzt leider zu spät.

Ein Tipp an alle, die ein Crossposting feststellen: Falls es im Thread nicht bemerkt wird, kann man gerne auch einen Moderator mit dem Melde-Button auf das Problem aufmerksam machtn.

Vielen Dank.

smile

Neue Frage »

Antworten »

Doppelpost! Rekursionsgleichung mit enthaltener Summe

Verwandte Themen