| Autor |
Beitrag |
    
anonym
| | Veröffentlicht am Samstag, den 28. April, 2001 - 21:21: | 
|
Aus reinem Interesse:
Wer kann mir bitte, den Induktionsbeweis führ die bekannte Formel:
Summenzeichen i i=1
(über dem Summenzeichen: n)
ist gleich (n/2)(n+1)
noch einmal aufschreiben?
Vielen Dank! |
J
| | Veröffentlicht am Sonntag, den 29. April, 2001 - 08:38: |
|
Ist ganz einfach!
Induktionsanfang:
der satz ist offensichtlich wahr für n= 1, da 1=1 wahr ist.
Induktionsvoraussetzung:
Der Satz sei wahr für irgendein n, d.h.
1+2+3+...+n = n*(n+1)/2
Induktionsschritt:
1+2+3+...+n+(n+1) = n*(n+1)/2 +(n+1)
= [n*(n+1)+2*(n+1)]/2
= [(n+2)*(n+1)]/2
q.e.d
Gruß J |
anonym
| | Veröffentlicht am Sonntag, den 29. April, 2001 - 10:13: |
|
Danke vielmahls, J!
An alle anderen: weitere Darstellungen wären von Interesse! |
Matroid (Matroid)
| | Veröffentlicht am Sonntag, den 29. April, 2001 - 22:51: |
|
Einiges über Induktionsbeweise findest Du bei
Prinzip der vollständigen Induktion |
anonym
| | Veröffentlicht am Dienstag, den 01. Mai, 2001 - 17:59: |
|
Vielen Dank, Matroid, der Link ist fantastisch. |
anonym
| | Veröffentlicht am Mittwoch, den 02. Mai, 2001 - 13:35: |
|
Man betrachte ein beliebiges, aus gleichen Quadraten zusammengesetztes Rechteck. Die beiden Seitenlängen "in Quadraten" nennen wir x, y .
Wieviele Rechtecke kann man nun in dieses Quadratgitter einzeichnen, sofern man auf den Linien zeichnet?
Die Lösung ist, dass man die bekannte Summenformel für x und für y verwendet, und beide Ergebnisse multipliziert. Also ist die Anzahl n der einzeichenbaren Rechtecke gleich
n= (((1/2)x)(x+1))(((1/2)y)(y+1))
Mein Problem besteht im Induktionsbeweis dieser Formel. Da man hier diese leicht beweisbare Summenformel zweimal mit unterschiedlichen Variablen verwendet, weiß ich nicht genau, wie man hier vorgehen soll. Beweist man sie mit einem stetigen x ? Wie geht man hier vor?
Vielen Dank! |
anonym
| | Veröffentlicht am Donnerstag, den 03. Mai, 2001 - 14:25: |
|
Bitte helft mir! Noch ist keine Antwort eingetroffen! |
Xell
| | Veröffentlicht am Donnerstag, den 03. Mai, 2001 - 16:41: |
|
Hallo anonym!
Wieso soll die Anzahl der einzuzeichnenden Rechtecke gleich Sx i=1i × Sy i=1i = 1/4×xy×(x+1)×(y+1) sein?
Ich verstehe deine Aufgabenstellung wahrscheinlich nicht recht. Wenn du das Ganze bitte einmal etwas präziser formulieren könntest, kann ich dir u.U. helfen...
mfG, Xell :-) |
anonym
| | Veröffentlicht am Donnerstag, den 03. Mai, 2001 - 17:12: |
|
Also, erst mal vielen Dank für Dein Interesse!
Mmm, Du verstehst die Aufgabenstellung nicht so recht. (übrigens entschuldige ich mich für meine Faulheit, keine ordentlichen Codes für das Sigma verwendet zu haben *g*)
Nimm Dir zu Beispiel ein Rechteck aus 2*3 gleichen Quadraten! Versuche nun herauszufinden, vieviele Rechtecke Du einzeichnen kannst! Also, die 6 kleinen Quadrate + die 3 senkrechten 2*1 Rechtecke + die 4 waagerechten 1*2 Rechtecke + die 2 2*2 Rechtecke + die 2 waagerechten 1*3 Rechtecke + das 1 große Rechteck = 6+3+4+2+2+1 = 18
So ist es gemeint. Man soll jedoch nicht so kopflos zählen, wie oben, sondern die Anzahl n direkt berechnen. Wenn mich nicht sehr, sehr viel täuscht, stimmt die Formel. Ich könnte sie jetzt auf mehrere Weisen erläutern, doch es geht mir um das Beweisen dieser Formel. Mich verwirren
schlicht die zwei Variablen.
Zum obigen Beispiel: n = 1/4 * xy * (x+1)* (y+1)
= 1/4 * 6 * 3 * 4
= 1/4 * 72
= 18
w |
Matroid (Matroid)
| | Veröffentlicht am Donnerstag, den 03. Mai, 2001 - 17:19: |
|
Ganz schön knifflig.
Beh. In einem rechteckigen Gitter mit x Spalten und y Zeilen lassen sich auf den
Gitterlinien zeichnend 1/2*x*(x+1)*1/2*y*(y+1) verschiedene Rechtecke einzeichnen.
Ich kürze obige Formel im folgenden mit R(x,y) ab. Damit das Gitter einen Sinn macht, müssen
x und y größer 0 sein.
Zuerst bemerke ich, daß offensichtlich R(x,y) = R(y,x) ist, denn die Anzahl der möglichen
Rechtecke bleibt gleich, wenn man die Begriffe "Zeile" und "Spalte" vertauscht.
Wir machen Induktion nach x+y, zeigen also, daß die Behauptung für x+y=2 gilt und daß unter
der Induktionsvoraussetzung "Anzahl Rechtecke in einem Gitter mit x Spalten und y Spalten =
R(x,y)" der Induktionschritt auf x+y+1 möglich ist.
Induktionsanfang: x+y=2 => Einziges mögliches Gitter besteht aus 1 Spalte und 1 Zeile. Es
ist R(x,y) = 1 und tatsächlich kann man nur ein Rechteck zeichnen.
Induktionsschluß: Ein rechteckiges Gitter mit Spalten und Zeilen sei gegeben und die Summe
der Anzahlen der Zeilen und Spalten sei gleich x+y+1.
Wir wissen nicht, aus wievielen Zeilen und Spalten das Gitter besteht, wir kennen nur deren
Summe. Damit wir aber rechnen und umformen können sei v die Anzahl der Spalten und w die
Anzahl der Zeilen. Natürlich muß gelten v>0 und w>0 und so wie es gemacht ist, ist v+w =
x+y+1.
Wir stellen uns dieses Gitter aufgezeichnet vor und markieren das rechte obere Quadrat
(machen es "rot").
Die Spalten und Zeilen numerieren wir von 1 bis v bzw. von 1 bis w, so daß das rote Quadrat
in der Spalte v und in der Zeile w liegt.
Die Anzahl der möglichen Rechtecke in diesem Gitter mit v Spalten und w Zeilen kann man nun
disjunkt aufteilen:
A = Menge der Rechtecke, die das rote Quadrat nicht enthalten.
B = Menge der Rechtecke, die das rote Quadrat enthalten.
Wir betrachten folgende Teilmengen der Menge A:
A1 = Menge der Rechtecke ohne ein Quadrat aus der Spalte v (die mit dem roten Quadrat)
A2 = Menge der Rechtecke ohne ein Quadrat aus der Zeile w (die mit dem roten Quadrat)
Weil es Rechtecke gibt, die weder ein Quadrat aus der Spalte v noch eines aus der Zeile w enthalten, ist das keine disjunkte Zerlegung.
Darum betrachten wir noch die Menge
A3 = Menge der Rechtecke ohne ein Quadrat aus der Zeile w und ohne ein Quadrat aus der Spalte v
Die Menge A1 ist die Menge der Rechtecke in einem Gitter mit v-1 Spalten und w Zeilen.
Die Menge A2 ist die Menge der Rechtecke in einem Gitter mit v Spalten und w-1 Zeilen.
Die Menge A3 ist die Menge der Rechtecke in einem Gitter mit v-1 Spalten und w-1 Zeilen.
Es gilt A3 = A1 geschnitten A2
In allen Fällen ist die Summe der Anzahl der Spalten und Zeilen kleiner v+w = x+y+1.
Also gilt nach Induktionsvoraussetzung:
|A| = |A1| + |A2| - |A3| = R(v-1,w) + R(v,w-1) - R(v-1,w-1)
Nun betrachten wir die Menge B genauer. Gesucht ist |B|.
Wenn das rote Quadrat in einem Rechteck enthalten ist, dann gehören 0 bis v-1 Quadrate der
Zeile w und 0 bis w-1 Quadrate der Spalte v dazu. Wir können alle Rechtecke zählen, wenn wir
jeweils eine Anzahl von Quadraten aus der Spalte v wählen (w Möglicheiten weil 0 bis w-1) und
anschließend die Anzahl der Quadrate aus der Zeile w wählen von keines bis alle, also v
Möglichkeiten.
=> Die Anzahl der Rechtecke mit dem roten Quadrat ist also gleich w*v = |B|.
Wir haben die Gesamtzahl der Quadrate in einem Gitter mit v Spalten und w Ecken berechnet
(dabei ist v+w=x+y+1):
|A|+|B| = R(v-1,w) + R(v,w-1) - R(v-1,w-1) + v*w
Schreiben wir die durch R(,) gemeinten Formel hin:
|A|+|B| = 1/4 * (v-1)*v * w*(w+1) + 1/4 * v*(v+1) * (w-1)*w - 1/4 * (v-1)*v * (w-1)*w + v*w
Nun kann man durch Termumformungen die Gleichheit mit dem zu beweisenden Ausdruck
1/2*v*(v+1)*1/2*w*(w+1) zeigen.
Gruß
Matroid |
Matroid (Matroid)
| | Veröffentlicht am Donnerstag, den 03. Mai, 2001 - 22:50: |
|
Weil ich die Aufgabe interessant finde und vielleicht noch ein Bild zur Erklärung erforderlich ist, habe ich alles bei http://matheplanet.de ins Web gestellt.
Falls es nicht oben steht, suche nach "Induktion Kombinatorik". |
anonym
| | Veröffentlicht am Samstag, den 05. Mai, 2001 - 11:22: |
|
Erst einmal vielen, vielen Dank für die enorm Umfangreiche Antwort! Mich verblüfft "Zahlreich.de" stets aufs neue.
Ich war auch bei Deinem Link, wo allerdings nur Grafiken hinzugefügt worden sind.
Desweiteren bin ich der selbe "anonym"! *g*
Ich habe jedoch noch eine ganze Reihe von Fragen:
1. Abgesehen von dem Beweis der von mir gegebenen Formel: wie würdest Du die Aufgabe selbst angehen; und mit welchem Ergebnis?
2. Ich kann nicht ganz glauben, dass man den Beweis so umständlich führen muss. Vielleicht irre ich mich aber auch. Ist vielleicht auch etwas anderes denkbar? Mir schwebte etwas in der Weise vor, dass man mit der Summenformel für die einzelnen Seitenlängen ja die Information über die einzeichenbaren Rechtecke der Form 1*x an beiden Seiten des Rechtecks erhält, un dann nur noch zeigen müsste, vielleicht mit Hilfe der Flächenberechnung eines Rechtecks (?), dass man durch die Multiplikation der beider Ergebnisse dann sämtliche Kombinationen erhält. Was sagst Du dazu?
3. Stimmt es, dass bei dem von Dir vorgeschlagenen Induktionsbeweis die sogenannte "konstruktive Idee" für den Induktionsschritt seine Länge ausmacht?
4. War Dir die Aufgabe geläufig?
Ciao! |
Matroid (Matroid)
| | Veröffentlicht am Samstag, den 05. Mai, 2001 - 12:09: |
|
Hallo Anonym,
auf die Frage 1 weiß ich keine Antwort. Ich bin die Aufgabe so angegangen, wie ich sie angegangen bin. Das Ergbnis steht ja fest, nämlich der Beweis der aufgestellten Formel. Und auch wenn nicht ausdrücklich ein Induktionsbeweis verlangt gewesen wäre, hätte ich einen Induktionsbeweis gemacht.
Zum Punkt 2: Ist der Beweis umständlich? Oder ist die Aufgabe schwierig. Für mich letzteres.
Wenn man statt eines allgemeinen x*y Gitters ein x*k Gitter mit festen k betrachtete und die Induktion über x machte, dann kann man zwar auch das Gitter zerlegen. Bei der Zerlegung tritt ein Gitter mit x-1 Spalten und k Zeilen auf, auf das die Induktionsvoraussetzung angewendet werden kann. Aber dieser Ansatz führt leider auch auf ein Gitter mit x Spalten und k-1 Zeilen. Und da bleibt man stecken. Denn aufgrund der Induktionsvoraussetzung kann man für ein Gitter mit x Spalten und k-1 Zeilen nur dann etwas sagen, wenn k-1 < x ist.
Im Fall k-1>=x ist man dagegen am Ende.
Frage 3: Na ja, die Länge eines Beweises ist vom Problem abhängig. Die konstrutive Idee muß zum Problem passen. Also hängt beides (die Länge und die Idee) vom Problem ab, aber Länge und Idee sind deshalb nicht notwendig voneinander abhängig.
Frage 4: Nein. Aber die von mir angewendete Idee ist typisch auch für ähnliche Aufgaben.
Gruß
Matroid |
habac
| | Veröffentlicht am Samstag, den 05. Mai, 2001 - 14:47: |
|
Also ich würde dieses Problem - wenn es nicht ausdrücklich verlangt ist - nicht mit vollst. Induktion, sondern als einfache Kombinatorikaufgabe lösen:
Ein mögliches Rechteck ist die Schnittfigur eines waagrechten und eines senkrechten Streifens.
Um den waagrechten Streifen zu bestimmen, muss man von den y+1 waagrechten Linien 2 auswählen, Reihenfolge unwesentlich, ohne Wiederholungen. Dazu gibt es y(y+1)/2 Möglichkeiten (Formel für Kombinationen bzw. ungeordete Stichproben).
Für den senkrechten Streifen erhält man analog x(x+1)/2 Möglichkeiten.
Also total das Produkt der beiden Zahlen.
Gruss
habac |
Matroid (Matroid)
| | Veröffentlicht am Samstag, den 05. Mai, 2001 - 17:47: |
|
Du hast recht, habac.
Gruß
Matroid |
anonym :-
| | Veröffentlicht am Samstag, den 05. Mai, 2001 - 22:05: |
|
Vielen Dank, habac, vielen Dank matroid!
Mir wurde jetzt erst klar, dass es sich in gewisser Weise um ein Missverständnis handelte.Es war kein Induktionsbeweis, sondern irgendein Beweis gefordert.
Könnte mir denn einer von Euch beiden die kombinatorische Lösung vielleicht noch einmal ausführlicher beschreiben. Sie gefällt mir. So wollte ich die Formel ja auch beweisen, mir fehlte das Wissen über Kombinatorik.
Ciao! |
|
