Damit das Gitter einen Sinn macht, müssen x und y größer 0 sein.
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 formulieren und rechnen können nennen wir die Anzahl der Spalten v und die Anzahl der Zeilen w.
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.
Abbildung 2: Das Quadrat links oben färbe rot. Das rote Quadrat ist in Spalte v=6 und Zeile w=4.
Die Anzahl der möglichen Rechtecke in diesem Gitter mit v Spalten und w Zeilen kann man nun disjunkt aufteilen in:
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
A2 = Menge der Rechtecke ohne ein Quadrat aus der Zeile w
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 formulieren wir noch die Schnittmenge von A1 und A2
A3 = Menge der Rechtecke ohne ein Quadrat aus der Zeile w und ohne ein Quadrat aus der Spalte v
Abbildung 3: Zählen der Rechtecke in verschiedenen Teilgittern mit weniger Spalten und Zeilen
Die Menge A1 ist die Menge der Rechtecke in einem Gitter mit v-1 Spalten und w Zeilen
(im grün und gelb markierten Teil des Gitters)
Die Menge A2 ist die Menge der Rechtecke in einem Gitter mit v Spalten und w-1 Zeilen.
(im grün und blau markierten Teil des Gitters)
Die Menge A3 ist die Menge der Rechtecke in einem Gitter mit v-1 Spalten und w-1 Zeilen.
(im grün markierten Teil des Gitters)
Es gilt A3 = A1 Ç 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)Bis hierhin haben wir alle Rechtecke, die das rote Rechteck nicht enthalten, gezählt, bzw. wir haben eine rekursive Formel für die Berechnung dieser Rechtecke gefunden.
Nun betrachten wir die Menge B genauer. B ist die Menge der Rechecke, die das rote Quadrat enthalten. 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|.
Damit können wir die Gesamtzahl der Quadrate in einem Gitter mit v Spalten und w Ecken angeben als (mit 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*wNun kann man durch Termumformungen die Gleichheit mit dem zu beweisenden Ausdruck
R(v,w) = 1/2*v*(v+1)*1/2*w*(w+1)zeigen.
q.e.d.
