Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweise durch vollständige Induktion

Beweise durch vollständige Induktion

Schüler Fachoberschulen, 12. Klassenstufe

Tags: Vollständig Induktion

Usavich aktiv_icon

12:37 Uhr, 27.10.2013

Hallo Leute,
ich brauche eure Hilfe bei dieser Aufgabe.

Beweise durch vollständige Induktion über

n \in N

n

Geraden in der Ebene schneiden sich in maximal

\frac{n \cdot (n - 1)}{2}

Punkten

Könnt ihr mir zunächst mal sagen, was die Aufgabestellung genau bedeutet? Ich weiß nämlich nicht, wie ich anfangen soll.

Danke im Voraus

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Shipwater aktiv_icon

12:52 Uhr, 27.10.2013

Bei vollständiger Induktion fängt man doch mit dem Induktionsanfang an. Bei

n = 1

hast du nur eine Gerade, da ist also kein Schnittpunkt möglich. Tatsächlich ist

\frac{1 \cdot (1 - 1)}{2} = 0

. Für die Anschauung kannst du dir das auch noch für paar weitere

n \in ℕ

überlegen. Nun kommt der Induktionsschritt, hast du da eine Idee? Achja und die Aufgabe setzt voraus, dass man bei identischen Geraden nicht von Schnittpunkten spricht. Sonst wären ja ab

n = 2

auch unendlich viele möglich.

Usavich aktiv_icon

12:58 Uhr, 27.10.2013

Hey shipwater,
zunächst danke für deine Antwort.

könnte man

n = 2

als Induktionsanfang beginnen? Wenn

n

bei

n = 1

nicht möglich ist, fängt man bei

n \in N

den nächst größeren Zahl an und das ist die 2 oder?

Shipwater aktiv_icon

13:01 Uhr, 27.10.2013

Du sollst die Aussage für alle

n \in ℕ

zeigen, also muss der Induktionsanfang für

n = 1

gemacht werden. Wie das geht habe ich dir oben ja schon gezeigt. Wenn du nur eine Gerade hast, ist kein Schnittpunkt möglich, also gibt es dann maximal

0 = \frac{1 \cdot (1 - 1)}{2}

Schnittpunkte, also stimmt die Behauptung für

n = 1

Usavich aktiv_icon

13:02 Uhr, 27.10.2013

achso ja stimmt. und bei induktionsschritt

n + 1

stimmt?

Usavich aktiv_icon

13:09 Uhr, 27.10.2013

Hmm stimmt, wie du schon erwähnt hast, bei identischen Geraden geht das irgendwie nicht. Man hat dann viele unendliche Punkte.

Usavich aktiv_icon

13:19 Uhr, 27.10.2013

ich habe leide keine Idee:(

Shipwater aktiv_icon

13:33 Uhr, 27.10.2013

Im Induktionsschritt setzt du voraus, dass die Aussage für ein festes

n \in ℕ

gilt also dass

n

Geraden maximal

\frac{n (n - 1)}{2}

Schnittpunkte haben. Nun willst du daraus folgern, dass

n + 1

Geraden dann maximal

\frac{(n + 1) n}{2}

Schnittpunkte haben können. Überlege dir dafür wie viele neue Schnittpunkte die (n+1)-te Gerade erzeugen kann.

Usavich aktiv_icon

13:41 Uhr, 27.10.2013

Vielleicht eine dumme Frage von mir. Wie kommst du auf

\frac{(n + 1) \cdot n}{2}

Shipwater aktiv_icon

13:53 Uhr, 27.10.2013

Jedes

n

durch

n + 1

ersetzen in

\frac{n (n - 1)}{2}

Usavich aktiv_icon

14:02 Uhr, 27.10.2013

Ich muss zugeben, das war wirklich eine dumme Frage von mir:-)

Nun zu Induktionsschritt:
Zu Zeigen:

n + 1 \in N = \frac{(n + 1) \cdot n}{2}

n + 1 = \frac{(n + 1) \cdot 2}{2}

hmm wie mache ich dann weiter?

Ich muss

n + 1

irgenwie ausrechenen bis ich auf der rechte Seite

\frac{(n + 1) \cdot 2}{2}

habe oder?

Shipwater aktiv_icon

14:13 Uhr, 27.10.2013

Hä was veranstaltest du denn da? Ich hab weiter oben schonmal geschrieben was du dir im Induktionsschritt zu überlegen hast, scroll mal hoch und lies.

Usavich aktiv_icon

14:18 Uhr, 27.10.2013

Das wird doch bei der vollständige Induktion so oder?

bei der Induktionsanfang haben wir ja bewiesen, dass wenn es eine Gerade vorhanden ist, die maximale Schnittpunkte 0 ist. Und das ist vollkommen wahr. Vielleicht sollte ich das Gleichheitszeichen weglassen. Und nun zu Induktionsschritt ist zu beweisen, wie viele

n + 1

Gerade die maximale Schnittpunkte haben. So habe ich verstanden.

Shipwater aktiv_icon

14:27 Uhr, 27.10.2013

Nope, ich kopiere: Im Induktionsschritt setzt du voraus, dass die Aussage für ein festes

n \in ℕ

gilt also dass

n

Geraden maximal

\frac{n (n - 1)}{2}

Schnittpunkte haben. Nun willst du daraus folgern, dass

n + 1

Geraden dann maximal

\frac{(n + 1) n}{2}

Schnittpunkte haben können. Überlege dir dafür wie viele neue Schnittpunkte die (n+1)-te Gerade erzeugen kann.

Usavich aktiv_icon

14:35 Uhr, 27.10.2013

Zu meiner Überlegung:
Ich habe einfach mal irgendeine Zahl in

n

eingesetzt habe konnte folgende feststellen.

n + 1 \to \frac{(n + 1) \cdot n}{2}

2 \to 1 + 1 \to 1

3 \to 2 + 1 \to 3

4 \to 3 + 1 \to 6

5 \to 4 + 1 \to 10

6 \to 5 + 1 \to 15

Die Zahlen

1,3,6,10,15

sind die Schnittpunkten zu jeweilige Geraden
1 zu 3 (plus

2)

3 zu 6 (plus

3)

6 zu

10

(plus

4)

10

15

(plus

5)

usw.

So wars meine Überlegung

Shipwater aktiv_icon

14:37 Uhr, 27.10.2013

Ist ja alles schön und gut, aber davor wirst du dich nicht drücken können: Überlege dir dafür wie viele neue Schnittpunkte die (n+1)-te Gerade erzeugen kann.

Usavich aktiv_icon

14:40 Uhr, 27.10.2013

Mir fällt nicht ein, ehrlich gesagt

: (

wenn

n = 3

hat sie maximal 3 schnittpunkte,

n = 4

maxiaml 6 schnittpunkte usw etwa so?

Shipwater aktiv_icon

14:44 Uhr, 27.10.2013

Du betrachtest jetzt kein festes

n \in ℕ,

sondern ein beliebiges! Also du hast schon

n

Geraden gegeben (diese haben laut IV maximal

\frac{n (n - 1)}{2}

Schnittpunkte) und jetzt kommt noch eine weitere (n+1)-te Gerade hinzu. Wie viele weitere Schnittpunkte können dadurch erzeugt werden?

Usavich aktiv_icon

14:47 Uhr, 27.10.2013

\frac{n \cdot (n + 1)}{2}

schnittpunkte?

Shipwater aktiv_icon

14:57 Uhr, 27.10.2013

Nicht raten. Mit welcher Begründung kommst du darauf?

Usavich aktiv_icon

14:59 Uhr, 27.10.2013

Meine Begründung
Dein Zitat: Du betrachtest jetzt kein festes

n \in N,

sondern ein beliebiges! Also du hast schon

n

Geraden gegeben (diese haben laut IV maximal

\frac{n \cdot (n - 1)}{2}

Schnittpunkte) und jetzt kommt noch eine weitere (n+1)-te Gerade hinzu. Wie viele weitere Schnittpunkte können dadurch erzeugt werden?

n + 1 \to \frac{n \cdot (n + 1)}{2}

(maximale Schnittpunkte)

Usavich aktiv_icon

15:09 Uhr, 27.10.2013

Ist es tatsächlich richtig?

Shipwater aktiv_icon

15:29 Uhr, 27.10.2013

Ich denke das wird nichts mehr daher löse ich auf. Wenn du

n

Geraden hast, die

\frac{n (n - 1)}{2}

Schnittpunkte haben (laut IV ist das die maximal mögliche Anzahl) und dann eine weitere dazu kommt und diese so gewählt ist, dass sie zu keiner der ersten