Vollständige Induktion

23.01.2011, 19:21	User5001	Auf diesen Beitrag antworten »
Vollständige Induktion Meine Frage: Beschäftige mich gerade etwas mit Vollständiger Induktion und komme nicht weiter. Die Aufgabe ist: Frage: Wieviele Möglichkeiten $\begin{eqnarray} b(n) \end{eqnarray}$ gibt es aus $\begin{eqnarray} n \end{eqnarray}$ Personen 4 für eine Bridgerunde auszuwählen? Antwort: Für alle $\begin{eqnarray} n \geq 4 \end{eqnarray}$ gilt $\begin{eqnarray} b(n) = \frac{n(n-1)(n-2)(n-3)}{24} \end{eqnarray}$ . Diese Formel soll nun per volständiger Induktion bewiesen werden. Meine Ideen: Ich habe versucht, mich an folgenden, ähnlichen Aufgaben zu orientieren: 1. Frage: Party mit n Gästen, jeder stößt mit jedem an. Wie oft klingen die Gläser? Antwort: Für alle $\begin{eqnarray} n\geq 1 \end{eqnarray}$ gilt: Es klingelt genau $\begin{eqnarray} k(n)=\frac{n(n-1)}{2} \end{eqnarray}$ mal. Kommt ein Gast später: $\begin{eqnarray} k(l + 1) = k(l) + l= \frac{l(l-1)}{2} +l = \frac{l(l-1)+2l}{2} = \frac{l(l+1)}{2} = \frac{(l+1)l}{2} \end{eqnarray}$ . Und noch eine andere Aufgabe: 2. Frage: Die Gäste wollen Skat spielen, aber es gibt nur ein Kartenspiel. Wieviele Möglichkeiten s(n) gibt es, aus n Personen 3 Spieler für eine Skatrunde auszuwählen? (Die Aufgabe ist also fast wie die, die ich lösen möchte). Antwort: Für alle $\begin{eqnarray} n\geq 1 \end{eqnarray}$ gilt $\begin{eqnarray} s(n) = \frac{n(n-1)(n-2)}{6} \end{eqnarray}$ . Beweisbar mithilfe der ersten Aufgabe (falls ein Gast hinzukommt, gilt $\begin{eqnarray} \frac{l(l-1}{2} \end{eqnarray}$ ): $\begin{eqnarray} s(l+1) = s(l) + \frac{l(l-1)}{2} = \frac{l(l-1)(l-2)}{6} + \frac{l(l-1)}{2} \end{eqnarray}$ ist nach kürzen und umformen: $\begin{eqnarray} = \frac{(l+1)l(l-1)}{6} \end{eqnarray}$ Nach diesem Schema habe ich auch versucht meine Aufgabe zu Beweisen, indem ich versucht habe $\begin{eqnarray} b(n+1) = \frac{n(n-1)(n-2)(n-3)}{24} + \frac{l(l-1)}{2} \end{eqnarray}$ zu rechnen, komme aber nicht auf das richtige Ergebnis. Ich hoffe mir kann jemand helfen Danke schonmal.
23.01.2011, 19:47	Eierkopf	Auf diesen Beitrag antworten »
RE: Vollständige Induktion Bilde doch mal die Differenz aus b(n+1) und b(n). Stimmt dann der von Dir benutzte Term noch? Übrigens gehört zu jeder Vollst. Induktion auch ein Induktionsanfang.
23.01.2011, 20:51	User5001	Auf diesen Beitrag antworten »
Nein, stimmt irgendwie alles nicht. Ich habe $\begin{eqnarray} b(4) = \frac{4(4-1)(4-2)(4-3)}{24} = 1 \end{eqnarray}$ und $\begin{eqnarray} b(5) = \frac{5(5-1)(5-2)(5-3)}{24} = 5 \end{eqnarray}$ und dann $\begin{eqnarray} b(4+1) = \frac{4(4-1)(4-2)(4-3)}{24} + \frac{4(4-1)}{2} = 7 \end{eqnarray}$ Es stimmt also nicht :/ Oder habe ich was übersehen?!
23.01.2011, 23:20	Mathorius	Auf diesen Beitrag antworten »
Reicht es nicht, wenn man n+1 einfach einsetzt, also IA: Man braucht mindestens 4 Personen für ein Bridge-Spiel. Also für alle $\begin{eqnarray} n \geq 4<br /> \end{eqnarray}$ gilt $\begin{eqnarray} b(n) = \frac{n(n-1)(n-2)(n-3)}{24} \end{eqnarray}$ . Da b(4) = 1 stimmt (man braucht ja mindestens 4) und $\begin{eqnarray} b(4) = \frac{4(4-1)(4-2)(4-3)}{24} = 1 \end{eqnarray}$ auch stimmt: IS: Die Formel stimmt bei $\begin{eqnarray} n\geq 4 \end{eqnarray}$ Personen. IV: Die Formel gilt auch für alle n+1. Beweis: Reicht es nicht, hier einfach n+1 anstelle von n einzusetzen!??! Also: $\begin{eqnarray} b(4+1) = \frac{(4+1)((4+1)-1)((4+1)-2)((4+1)-3)}{24} = 5 \end{eqnarray}$ was das gleiche ist wie $\begin{eqnarray} b(5) = \frac{5(5-1)(5-2)(5-3)}{24} = 5 \end{eqnarray}$ IB:* Die Formel stimmt also für $\begin{eqnarray} n\geq 4 \end{eqnarray}$ . q.e.d. Wäre das eine komplette vollständige Induktion?
24.01.2011, 12:12	User5001	Auf diesen Beitrag antworten »
Danke für die Antwort. Ich glaube ganz so einfach ist es nicht. Vielleicht kann ja noch jemand was dazu sagen?
24.01.2011, 12:19	Iorek	Auf diesen Beitrag antworten »
Wenn du n+1 einsetzen willst, wieso setzt du 4+1=5 ein? Nein, das ist kein gültiger Beweis.
Anzeige

24.01.2011, 13:04	User5001	Auf diesen Beitrag antworten »
Wie müsste ich denn vorgehen? Frage: Wieviele Möglichkeiten $\begin{eqnarray} b(n) \end{eqnarray}$ gibt es aus $\begin{eqnarray} n \end{eqnarray}$ Personen 4 für eine Bridgerunde auszuwählen? Antwort: Für alle $\begin{eqnarray} n \geq 4 \end{eqnarray}$ gilt $\begin{eqnarray} b(n) = \frac{n(n-1)(n-2)(n-3)}{24} \end{eqnarray}$ . Beweise mit vollständiger Induktion. Nun muss ich das Ganze wohl für n+1 zeigen. Ich dachte n+1 ist $\begin{eqnarray} \frac{n(n-1)}{2} \end{eqnarray}$ , aber das scheint nicht so zu sein...
24.01.2011, 19:18	User5001	Auf diesen Beitrag antworten »
Ok, ich weiß inzwischen, dass $\begin{eqnarray} b(n+1) = \frac{n(n-1)(n-2)(n-3)}{24} + \frac{n(n-1)(n-2)}{6} \end{eqnarray}$ ist, bin mir aber noch nicht ganz sicher, wie ich das in die Form das vollständigen Induktion kriege. Ich hoffe, dabei kann mir jemand helfen?!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »