Rekursion beweisen < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Eine Gruppe von n Personen [mm] (n\in\IN) [/mm] zusammen und jeder der n Personen schüttelt jeder anderen Person die Hand.
Wie oft werden die Hände geschüttelt? Finden Sie eine rekursive Beschreibung der Anzahl und lösen Sie die Rekursion auf. |
Ich hab jetzt folgende Rekursion entwickelt:
1+2+3+...+n-1=(n(n-1))/2
Es gilt die Rekursion an=(n(-1))/2 für n=1,2,3...
Reicht das zum finden einer rekursiven Beschreibung oder muss ich diese noch beweisen?
Wie löse ich diese nun auf?
|
|
| |
|
Hallo missjanine,
> Eine Gruppe von n Personen [mm](n\in\IN)[/mm] zusammen und jeder der
> n Personen schüttelt jeder anderen Person die Hand.
> Wie oft werden die Hände geschüttelt? Finden Sie eine
> rekursive Beschreibung der Anzahl und lösen Sie die
> Rekursion auf.
>
> Ich hab jetzt folgende Rekursion entwickelt:
> 1+2+3+...+n-1=(n(n-1))/2
Das ist keine Rekursion, das ist die Auflösung.
> Es gilt die Rekursion an=(n(-1))/2 für n=1,2,3...
![[haee]](/images/smileys/haee.gif "[haee]") Das verstehe ich nicht.
Eine rekursive Definition wäre wie folgt:
Nehmen wir an, für (n-1) Personen sei die Anzahl des Händeschüttelns [mm] $a_{n-1}$. [/mm] Nun betritt eine n-te Person den Raum. Alle andern haben sich schon begrüßt, also muss nur noch Person n allen (n-1) andern die Hand geben.
Also ist [mm] $a_n=a_{n-1}+(n-1)$.
[/mm]
Weiter wissen wir: [mm] $a_1=0$.
[/mm]
So. Und jetzt leite daraus mal Deine (richtige) explizite Darstellung her.
> Reicht das zum finden einer rekursiven Beschreibung oder
> muss ich diese noch beweisen?
Nein, so wie bei Dir reicht es garantiert nicht.
Natürlich kannst Du Deine Formel aus dem Hut zaubern und zeigen, dass die Rekursionsformel dann stimmt und [mm] a_1 [/mm] auch richtig berechnet wird, aber eine schöne Lösung mit Herleitung ist das dann nicht.
> Wie löse ich diese nun auf?
Du gehst falsch herum vor. Du fängst mit der expliziten Form an.
Weißt Du, was "Rekursion" eigentlich heißt, und kannst Du sie in eigenen Worten definieren?
Grüße
reverend
|
|
|
| |
|
Mein Plan war nun durch vollständige Induktion die Rekursion an=an-1+(n-1) aufzulösen.
Behauptung: an=(n*(n-1))/2
Induktionsanfang: Für n=1 gilt a1=0=(1*(1-1))/2
Induktionsannahme:
Sei [mm] n\in\{2,3,...\} [/mm] und es gelte an=an-1+(n-1)=(n*(n-1))/2
Induktionsschluss:
Da 0+1+3+...+an+an+1=((n+1)*(n-2))/2 ist, muss ich doch folgendes beweisen?
((n+1)*(n-2))/2=(n+(n-1))/2+an+1
Doch mich stört das an? Irgendwie komm ich nicht weiter...
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:16 Mo 05.11.2012 | | Autor: | leduart |
Hallo
schwer zu lesen: nach dem Unterstrich alles, was länger als 1 zeichen ist in eckige Klammern setzen.
du hast hoffentlich mit Begründung [mm] a_n=a_{n-1}+n-1
[/mm]
du willst zeigen: [mm] a_n=n*{n-1}/2
[/mm]
Indanfang, richtig für [mm] a_1
[/mm]
ind, Vors richtig für [mm] a_n, [/mm] d.h. es gilt [mm] a_n=n*{n-1}/2
[/mm]
daraus folgern für [mm] a_{n+1}=(n+1)*n/2
[/mm]
[mm] bekannt:a_{n+1}=a_n+n
[/mm]
Indvors einstzen: [mm] a_{n+1}=n*(n-1)/2+n
[/mm]
daraus jetzt ausrechnen dass das (n+1)*n/2 ist.
du musst bei der ind. systematischer vorgehen.
klar sagen, was benutzt wird, was Vors, was Behauptung, was bekannt (hier die Rekursion).
Grus leduart
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:24 Mo 05.11.2012 | | Autor: | reverend |
Hallo leduart,
> schwer zu lesen: nach dem Unterstrich alles, was länger
> als 1 zeichen ist in eckige Klammern setzen.
Wohl wahr. Hier kann $an-1$ offenbar für alles mögliche stehen:
$a*n-1$ oder [mm] a_n-1 [/mm] oder auch [mm] a_{n-1}
[/mm]
Da muss man sich die Wahrheit zurechtlesen.
> du hast hoffentlich mit Begründung [mm]a_n=a_{n-1}+n-1[/mm]
> du willst zeigen: [mm]a_n=n*{n-1}/2[/mm]
Nein, sie will zeigen: [mm] a_n=\bruch{n*(n-1)}{2}
[/mm]
> Indanfang, richtig für [mm]a_1[/mm]
> ind, Vors richtig für [mm]a_n,[/mm] d.h. es gilt [mm]a_n=n*{n-1}/2[/mm]
Siehe oben.
> daraus folgern für [mm]a_{n+1}=(n+1)*n/2[/mm]
> [mm]bekannt:a_{n+1}=a_n+n[/mm]
> Indvors einstzen: [mm]a_{n+1}=n*(n-1)/2+n[/mm]
> daraus jetzt ausrechnen dass das (n+1)*n/2 ist.
> du musst bei der ind. systematischer vorgehen.
> klar sagen, was benutzt wird, was Vors, was Behauptung,
> was bekannt (hier die Rekursion).
Grüße
reverend
|
|
|
|
