Angenommen, Sie sind mit neun anderen Leuten auf einer Party und jeder schüttelt jedem genau einmal die Hand. Wie viele Handschläge finden statt?

Das ist das „Handshake-Problem“, und es ist eines meiner Lieblingsprobleme. Als Mathematiklehrer liebe ich es, weil es so viele verschiedene Möglichkeiten gibt, zur Lösung zu gelangen, und die Vielfalt und Vernetzung dieser Strategien veranschaulicht wunderbar die Kraft des kreativen Denkens in der Mathematik.

Eine Lösung sieht so aus: Beginnen Sie damit, dass jede Person jeder anderen Person die Hand schüttelt. Zehn Personen mit jeweils neun Handschlägen erzeugen insgesamt 9 × 10 = 90 Handschläge. Dabei wird jedoch jeder Handshake zweimal gezählt – einmal aus der Sicht jedes Shakers –, sodass die tatsächliche Anzahl der Handshakes $latex frac{90}{2} = 45$ beträgt. Ein einfaches und schönes Zählargument für den Sieg!

Es gibt auch einen ganz anderen Weg, das Problem zu lösen. Stellen Sie sich vor, dass die Gäste einzeln ankommen und dort allen Anwesenden die Hand schütteln. Die erste Person hat keine Hände zum Händeschütteln, daher gibt es in einer Ein-Personen-Gruppe überhaupt keinen Händedruck. Nun kommt die zweite Person und schüttelt der ersten Person die Hand. Dies erhöht die Gesamtzahl um einen Handschlag, sodass es bei einer Zweiergruppe insgesamt 0 + 1 = 1 Handschlag gibt. Wenn die dritte Person eintrifft und den ersten beiden Gästen die Hand schüttelt, addiert sich die Gesamtzahl um zwei Handschläge. Die Ankunft der vierten Person erhöht die Gesamtzahl um drei Händeschütteln und so weiter.

Diese Strategie modelliert die Abfolge von Handshakes rekursiv, was bedeutet, dass jeder Begriff in der Abfolge relativ zu den davor stehenden Begriffen definiert wird. Sie kennen wahrscheinlich die Fibonacci-Folge, die berühmteste rekursive Folge überhaupt. Es beginnt mit 1, 1, 2, 3, 5, 8, 13, 21 und wird fortgesetzt, wobei jeder weitere Term der Summe der beiden vorherigen entspricht.

Wie wir weiter unten sehen werden, ist die Rekursion ein flexibler und leistungsstarker Rahmen zum Nachdenken über ein breites Spektrum mathematischer Ideen. Und obwohl alten indischen Gelehrten wie Hemachandra zugeschrieben wird, dass sie bereits im Jahr 1150 über diese Art von Sequenzen Bescheid wussten, stellen sie auch heute noch faszinierende Herausforderungen für Mathematiker dar.

Sehen wir uns an, wie rekursives Denken beim Handshake-Problem hilft. Wenn wir $latex a_n$ gleich der Anzahl der Handshakes bei an lassen n-Personenpartei können wir diese rekursive Beziehung mit der folgenden Formel darstellen:

$latex a_n = a_{n-1} + n–1$

Dies sagt uns, dass die Anzahl der Handshakes bei einem n-Personenparty ($latex a_n$) ist gleich der Anzahl der Handshakes bei einem (n − 1)-Personen-Gruppe ($latex a_{n-1}$) plus n − 1 weiterer Handschlag, der die Idee widerspiegelt, dass, wenn eine neue Person ankommt, sie zu den bereits erfolgten Handschlägen eine bestimmte Anzahl weiterer Handschläge hinzufügt.

In unserer speziellen Version des Handshake-Problems möchten wir $latex a_{10}$ wissen, die Anzahl der Handshakes auf einer Party mit 10 Personen. Um herauszufinden, dass wir die rekursive Beziehung verwenden

$latex a_{10} = a_9 + 9$

Um den Wert von $latex a_{10}$ zu ermitteln, müssen wir lediglich den Wert von $latex a_9$ kennen und 9 dazu addieren. Wie finden wir den Wert von $latex a_9$? Natürlich durch Rekursion!

$Latex a_9 = a_8 + 8$

Um nun den Wert von $latex a_8$ zu ermitteln, müssen wir den Wert von $latex a_7$ ermitteln, was die Kenntnis von $latex a_6$ erfordert, und so weiter. An diesem Punkt befürchten Sie vielleicht, dass dies in einer Art unendlichem Abstieg ewig so weitergehen wird, aber sobald wir $latex a_1$ erreicht haben, sind wir fertig, weil wir wissen, dass es bei einer Ein-Personen-Party insgesamt null Handshakes gibt.

$latex a_1 = 0$

Dieser Anfangs- oder „Startwert“ ist ein Schlüsselmerkmal einer rekursiven Sequenz. Es garantiert, dass dieser Prozess des Zurückverfolgens der Sequenz mithilfe der rekursiven Beziehung beendet wird. Sobald Sie den Startwert erreicht haben, stoppt das Zurückverfolgen, und Sie können sich dann durch die Liste vorwärts arbeiten, um den gewünschten Wert zu erhalten.

$latex a_1 = 0$

$Latex a_2 = a_1 + 1 = 0 + 1 = 1$

$Latex a_3 = a_2 + 2 = 1 + 2 = 3$

$Latex a_4 = a_3 + 3 = 3 + 3 = 6$

$Latex-Cdots$

$latex a_{10} = a_9 + 9 = 36 + 9 = 45$

Wenn wir die Liste durchgehen, sehen wir, dass es bei einer 45-köpfigen Party insgesamt 10 Handshakes gibt, was mit unserer ursprünglichen Berechnung übereinstimmt. Wenn Sie wie meine Schüler sind, fragen Sie sich vielleicht, warum wir einen anderen Weg zur Lösung dieses Problems brauchen, wenn wir die Antwort bereits kennen, insbesondere da dieser zweite Ansatz länger zu dauern scheint.

Das ist eine gute Frage. Eine Antwort ist, dass der rekursive Ansatz uns eine völlig andere Sicht auf das gibt, was bei diesem Problem vor sich geht, und dass unterschiedliche Perspektiven in der Mathematik wie in allen anderen Dingen nützlich sind. Sie geben uns verschiedene Möglichkeiten, Konzepte zu verstehen und ermöglichen uns die Verwendung verschiedener Tools, die helfen können, wenn wir nicht weiterkommen.

Insbesondere die Rekursion ist nützlich, weil sie überall in der Mathematik vorkommt. Es entsteht zum Beispiel in den linearen Beziehungen, die jeder im Mathematikunterricht lernt – diejenigen, die durch eine konstante Änderungsrate gekennzeichnet sind und durch Linien in der Ebene dargestellt werden. Eine lineare Funktion wie $latex f(x) = 3x + 5$ kann man sich als rekursive Formel vorstellen:

$latex a_0 = 5$

$latex a_n = a_{n-1} + 3$

Obwohl die offensichtlichere Art, über $latex f(2)$ nachzudenken, darin bestehen könnte, dass $latex f(2) = 3 mal 2 + 5 = 11$ ist, ist eine andere Möglichkeit, dass $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11$. Die rekursive Modellierung des grundlegenden Merkmals linearer Funktionen – der konstanten Änderungsrate – gibt uns eine andere Möglichkeit, über diese Beziehung nachzudenken. Dasselbe kann mit Exponentialfunktionen durchgeführt werden, die durch eine konstante multiplikative Änderung gekennzeichnet sind.

Rekursives Denken funktioniert auch über Zahlenfolgen hinaus. Wenn Sie jemals ein Gleichungssystem gelöst haben, haben Sie wahrscheinlich einen rekursiven Ansatz angewendet. Um das System zu lösen

$Latex 2x + y = 10$

$Latex 3x – y = 5$

Sie können zunächst die beiden Gleichungen addieren, um das zu eliminieren y Variable, die die Gleichung $latex 5x = 15$ ergibt. Lösen Sie dies, um $latex x =$ 3 zu erhalten, ersetzen Sie es, um $latex y = 4$ zu finden, und fertig. Dieser Ansatz nutzt einen rekursiven Algorithmus, bei dem die Lösung eines Systems aus der Lösung kleinerer, verwandter Systeme aufgebaut wird. Um beispielsweise ein 3×3-System zu lösen, eliminieren Sie eine Variable, um daraus ein 2×2-System zu machen, und dann noch einmal, um daraus ein 1×1-System zu machen. Diese einfach zu lösende einzelne Gleichung ist sozusagen der Ausgangswert dieses rekursiven Prozesses. Es signalisiert das Ende des Backtrackings, und von dort aus arbeiten Sie sich in der Gleichungskette wieder nach oben, genau wie in einer rekursiven Reihenfolge.

Es gibt sogar rekursive Beweistechniken. Eine berühmte Formel in der Geometrie ist beispielsweise die Polygonwinkelsummenformel, die besagt, dass die Summe der Maße der Innenwinkel eines n-seitiges Polygon ist $latex (n-2) mal 180^{circ}$. Eine Möglichkeit, dieses Ergebnis zu beweisen, besteht darin, mit einem zu beginnen n-gon und stellen Sie sich vor, was passieren würde, wenn Sie ein Dreieck entfernen würden.

Durch das Entfernen eines Dreiecks wird das n-gon in ein (n − 1)-gon, und es entfernt auch 180 Grad des Innenwinkelmaßes. Dies ist eine rekursive Beziehung: Die Innenwinkelsumme für an n-gon ist 180 Grad größer als die Innenwinkelsumme für ein (n − 1)-gon. Um das allgemeine Ergebnis zu ermitteln, entfernen Sie so lange Dreiecke, bis Sie den Startwert erreichen. Dies geschieht in dieser Situation, wenn Sie alle bis auf drei entfernt haben n-gons Eckpunkte. Zu diesem Zeitpunkt wurde das ursprüngliche Polygon auf ein Dreieck reduziert, dessen Innenwinkelsumme bekanntermaßen 180 Grad beträgt. Arbeiten Sie sich nun wieder nach oben vor und fügen Sie bei jedem Schritt 180 Grad hinzu, und Sie erhalten die Formel.

Zurück zu unserer Gruppe: Das Handshake-Problem selbst zeigt uns, was möglich ist, wenn wir kreativ denken und dann die verschiedenen Perspektiven eines Problems miteinander verbinden. Wenn wir mit dem rekursiven Modell für unsere Handshake-Sequenz herumspielen:

$latex a_1 = 0$

$latex a_n = a_{n-1} + n – 1$

Es entsteht ein schönes Muster:

$latex a_2 = a_1 + 1 = 0 + 1$

$latex a_3 = a_2 + 2 = 0 + 1 + 2$

$latex a_4 = a_3 + 3 = 0 + 1 + 2 + 3$

$Latex-Cdots$

$latex a_n = a_{n-1} + (n-1) = 0 + 1 + 2 + 3 + cdots + (n-1)$

Wir haben jetzt eine neue und allgemeine Möglichkeit, über das Problem nachzudenken: Die Anzahl der Handshakes in einem n-Personenpartei ist gleich der Summe der ersten n − 1 positive ganze Zahl.

Denken Sie an unseren ursprünglichen Ansatz zurück. In einem (n n-Personenparty, jede Person schüttelt der anderen Person die Hand n − 1 Personen. Das Produkt $latex n (n-1)$ zählt jeden Handshake zweimal, sodass die Gesamtzahl der Handshakes $latex frac{n(n-1)}{2}$ beträgt. Aber da unsere verschiedenen Methoden das Gleiche zählen, müssen sie zum gleichen Ergebnis führen. Dies bedeutet insbesondere:

$latex 1 + 2 + 3 + cdots + (n-1) = frac{n(n-1)}{2}$

Durch die Verbindung verschiedener Ansätze zum Handshake-Problem erhalten wir eine geschlossene Formel für die Summe des ersten n − 1 positive ganze Zahl. Aber wir bekommen noch mehr: Der Ausdruck $latex frac{n(n-1)}{2}$ beinhaltet einen Bruch, aber weil er gleich einer Summe von ganzen Zahlen ist, muss er auch eine ganze Zahl sein. Dies beweist eine einfache Tatsache der Zahlentheorie: Für jede ganze Zahl n, $latex frac{n(n-1)}{2}$ ist eine ganze Zahl.

Dieselbe Art von Argumentation treibt auch heute noch die moderne Mathematik an. Als ein Beispiel Forscher in den frühen 2000er Jahren erbrachte einige überraschende Ergebnisse über rekursive Folgen, die als Somos-Folgen bekannt sind, indem wir zeigen, dass auch sie etwas zählen. Durch die Kraft kreativer Verbindungen haben Mathematiker erneut herausgefunden, wohin sie gehen können, indem sie verstehen, wo sie waren.

Übungen

1. Finden Sie eine geschlossene Formel für die Sequenz, die rekursiv definiert ist als
$latex a_1 = 1$
$latex a_n = a_{n-1} + 2n – 1$

2. Am Ende der Spalte wurde gezeigt, dass der Ausdruck $latex frac{n(n-1)}{2}$ eine ganze Zahl ist, obwohl der Ausdruck einen Bruch beinhaltet, weil $latex frac{n(n-1 )}{2}$ ist das Ergebnis einer Zählung. Es gibt auch ein Argument der Zahlentheorie, das zeigt, dass dieser Ausdruck eine ganze Zahl sein muss. Was ist es?

3. Finden Sie die ersten paar Terme der rekursiven Folge
$latex a_1 = 1$
$latex a_n = frac{1}{1+a_{n-1}}$

4. Finden Sie die ersten paar Terme der rekursiven Folge
$latex a_1 = 1$
$latex a_2 = 1$
$latex a_n = a_{n-1} – a_{n-2}$