Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Vollständige Induktion eines Schachbretts

Vollständige Induktion eines Schachbretts

Universität / Fachhochschule

Tags: Vollständig Induktion

Tivot aktiv_icon

00:44 Uhr, 04.05.2020

Hallo,

ich habe folgende Aufgabe. Sie sollte eigentlich leicht zu lösen sein, aber irgendwie habe ich einen kleinen Hänger.

Aufgabe:

- - - - - - - - - - - - - - - - - - - -

In einem bekannten Märchen soll ein Mann von einem König eine Belohnung bekommen. Er bittet sich aus, ein Schachbrett mit Reiskörnern zu belegen: auf das erste Feld 1 Korn, auf das zweite 2 Körner, auf das dritte 4 Körner usw., immer das Doppelte. Der König willigte ein, weil er den Mann für bescheiden hielt. Er war es aber nicht.

Zeigen Sie: auf dem

n

. Feld liegen

2^{n - 1}

Reiskörner.

Tipp: Fassen sie das Schachbrett als ein Array

S (n)

auf, mit der Feldnummer

n = 1, ..., 64

als Index und der Anzahl Körner auf dem jeweiligen Feld als Wert. Dann ist zu zeigen:

S (n) = 2^{n - 1}

- - - - - - - - - - - - - - - - - - - -

Die Aufgabe soll übrigens ohne Summenzeichen gelöst werden.

Als Induktionsanfang habe ich

n = 1; S (1) = 2^{1 - 1}

(Ergebnis: links

= 1,

rechts

= 1)

Das klappt für

n = 1

. Setze ich aber

10

ein, klappt das natürlich nicht:

S (10)

ungleich

2^{10 - 1}

(links

= 10,

rechts

= 512)

.

Und jetzt stehe ich auf dem Schlauch. Ich kann ja wohl kaum weiter mit dem Beweis fortfahren, wenn ich weiß, dass das nur für

n = 1

richtig ist.

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

anonymous

07:50 Uhr, 04.05.2020

Hallo
Du hast die Aufgabe falsch abgeschrieben.
Es soll mit an Sicherheit grenzender Wahrscheinlichkeit heißen:

Dann ist zu zeigen:

S (n) = 2^{n} - 1

Tivot aktiv_icon

11:46 Uhr, 04.05.2020

Nein, das steht so.

Hier ein Bildschirmausschnitt der Originalaufgabe.

HAL9000

12:35 Uhr, 04.05.2020

Es steht ja deutlich da:

S (n)

ist die Anzahl der Körner AUF dem jeweiligen Feld. Also nicht die AnzahlSUMME BIS einschließlich

n

-tes Feld.

Vermutlich hat 11engleich Symbol

S

gleich mit Summe assoziiert. Deine Formulierung "ohne Summenzeichen" hat wohl auch dazu beigetragen. :-)

Tivot aktiv_icon

13:15 Uhr, 04.05.2020

Moment, das

n

indem

S (n)

ist schon die Anzahl der Körner auf dem Feld?

Das

n

ist aber der Index? Und der geht nur bis

64

? Mein Problem: Wie kann

S (10)

auch nur entfernt

= 2^{10 - 1}

sein?

Links ist

10,

rechts ist

512

. Wo ist mein Verständnisfehler hier?

ermanus aktiv_icon

13:31 Uhr, 04.05.2020

Hallo,
was ist denn so schwer daran zu verstehen?
Auf Feld 1 liegt 1 Korn, auf Feld 2 liegen 2 Körner, auf Feld 3 liegen 4 Körner, ...
Also

S (1) = 1, S (2) = 2, S (3) = 4, . . .

Tivot aktiv_icon

13:47 Uhr, 04.05.2020

Ja, das ist mir klar schon klar.

Aber muss links nicht gleich rechts sein? Ist das nicht Sinn der Sache beim Induktionsbeweis?

Also, Beispiel Gaußsche Summenformel:

1 + 2 + 3 + . .

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

Links und rechts sind hier eindeutig gleich.

S (3) = 4 ...

? Hier hapert es bei mir.

ermanus aktiv_icon

13:52 Uhr, 04.05.2020

Sei

T (n)

die Summe der Zahlen von

1

bis

n

.
Dann ist

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

.
Würdest du jetzt auch behaupten wollen, dass da eigentlich
dann doch

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

stehen müsste,
weil ja sonst links und rechts nicht dasselbe stünde????

Tivot aktiv_icon

14:00 Uhr, 04.05.2020

Hm, jetzt fängt es langsam an zu klicken.

"weil ja sonst links und rechts nicht dasselbe stünde????"

Also, der Kernsatz lautet, teste es für

1,

bzw.

0,

(Induktionsanfang) und dann stop?

Und wie lautet nun die Lösung der ursprünglichen Aufgabe?

ermanus aktiv_icon

14:07 Uhr, 04.05.2020

Nun, nach Voraussetzung weißt du, dass

S (n + 1) = 2 \cdot S (n)

ist,
da jedes Feld doppelt soviele Körner hat wie sein Vorgänger.
Den formalen Induktionsbeweis solltest du nun wirklich selbst versuchen
auszuformulieren.
Du kannst ihn dann ja gern hier "veröffentlichen", damit wir ihn
nochmal begutachten können ...

Gruß ermanus

Tivot aktiv_icon

14:20 Uhr, 04.05.2020

"Nun, nach Voraussetzung weißt du, dass

S (n + 1) = 2 \cdot S (n)

ist"

Langsam wird es mir etwas peinlich, aber was ist in der Zwischenzeit mit

2^{n - 1}

passiert?

(. .

. es liegen

2^{n - 1}

Reiskörner, dann ist zu zeigen:

S (n) = 2^{n - 1} .

.)

ermanus aktiv_icon

14:29 Uhr, 04.05.2020

Du willst doch folgende Aussage beweisen:

Für alle natürlichen Zahlen

n > 0

gilt

S (n) = 2^{n - 1}

Für

n = 1

hast du bereits eingesehn, dass

IA:

S (1) = 1 = 2^{1 - 1}

gilt.

Jetzt kommt als Nächstes die Induktionsvoraussetzung:

IV: Für eine natürliche Zahl

n > 0

gelte

S (n) = 2^{n - 1}

.

Wie lautet denn nun dein Induktionsschluss, also dein
Schluss von

n

auf

n + 1

Tivot aktiv_icon

14:33 Uhr, 04.05.2020

2 \cdot 2^{n - 1} = 2^{n}

ermanus aktiv_icon

14:34 Uhr, 04.05.2020

Ja. Aber das ist ein sehr magerer mathematischer Text ;-)
Das solltest du schon genauer ausführen ...

Tivot aktiv_icon

14:40 Uhr, 04.05.2020

IS:

S (n + 1) = 2 \cdot S (n) = 2 \cdot 2^{n - 1} = 2^{n}

ermanus aktiv_icon

14:47 Uhr, 04.05.2020

Ja. Das sieht schon sehr gut aus.
Aber ich zitiere nochmal die Aufgabenstellung:
"...Im letzteren notiern Sie zuerst, was genau zu zeigen ist.
Markieren Sie unbedingt, wo Sie (IV) verwenden ..."

Tivot aktiv_icon

14:56 Uhr, 04.05.2020

Ist die IV nicht im Wesentlichen die Wiederholung der Aufgabenstellung?

IV:

S (n) = 2^{n - 1}

ermanus aktiv_icon

14:59 Uhr, 04.05.2020

Da steht nicht, dass du die (IV) nochmal hinschreiben sollst, sondern
dass du klar machst, an welcher Stelle du sie verwendest.

Es geht jetzt darum, den mathematischen Text für (IS) "perfekt"
zu machen ...

Tivot aktiv_icon

15:04 Uhr, 04.05.2020

IS:

S (n + 1) = 2 \cdot S (n)

IV hier, für Herleitung zu

= 2 \cdot 2^{n - 1} = 2^{n}

ermanus aktiv_icon

15:10 Uhr, 04.05.2020

OK. Du meinst es ja richtig ...
Hier ein Vorschlag:

IS: es ist zu zeigen: (IV)

\Rightarrow S (n + 1) = 2^{n}

Bew.:

S (n + 1) = 2 \cdot S (n) =

wegen (IV)

= 2 \cdot 2^{n - 1} = 2^{n}

Tivot aktiv_icon

15:13 Uhr, 04.05.2020

Vielen Dank, hat mir sehr weitergeholfen.

Tivot aktiv_icon

17:16 Uhr, 04.05.2020

Mir fällt gerade ein, es gibt noch die Induktionsbehauptung (IB).

Was wäre die IB hier? Sollte man sie überhaupt aufstellen?

ermanus aktiv_icon

17:32 Uhr, 04.05.2020

Naja, das ist der Satz, den man beweisen möchte.
Den sollte man am Anfang nennen:

Behauptung:
blablabla

Beweis durch vollständige Induktion:
blublublu
...

Tivot aktiv_icon

17:52 Uhr, 04.05.2020

Und was wäre die korrekte IB hier?

IV:

S (n) = 2^{n - 1}

IB:

S (n + 1) = 2 \cdot S (n)

Stimmt?

ermanus aktiv_icon

18:01 Uhr, 04.05.2020

Nein.

In der Aufgabenstellung wird gegeben:

S (1) = 1

und

S (n + 1) = 2 \cdot S (n)

.
Das sind die in der Aufgabe vorgegebenen Voraussetzungen.

Und das ist die zu beweisende Behauptung:

"Für alle natürlichen Zahlen

n > 0

ist

S (n) = 2^{n - 1}

."

Dann kommt der

Beweis (mit vollst. Induktion):
....

Tivot aktiv_icon

18:12 Uhr, 04.05.2020

Kann man dann sagen:

IV:

S (n + 1) = 2 \cdot S (n)

IB:

S (n) = 2^{n - 1}

Übrigens, was kann man von diesem Video halten:

www.youtube.com/watch?v=BTNrSCDL2us

?

Ich habe das "Kochrezept" dort mit Beispielen, welche das Summenzeichen hatten, probiert, und es hat gut geklappt. Ich versuche die dort aufgezeigte Methode auf dieses Beispiel zu übertragen, das klappt aber nicht (die Endgleichung löst sich nicht auf).

ermanus aktiv_icon

18:20 Uhr, 04.05.2020

Nein.

S (n + 1) = 2 \cdot S (n)

ist keine Induktionsvoraussetzung,
sondern etwas, das in der Aufgabe als Grundtatsache gegeben ist.

2 \cdot 2^{n - 1} = 2^{n}

ist doch auch keine Induktionsvoraussetzung,
sondern einfach eine bekannte Tatsache.

Vollständige Induktion ist eine generelle Methode,
die in jedem speziellen Kontext anders gestaltet werden muss.
Du musst das Prinzip verstehen, nicht die Rezepte auswendig lernen,
die möglicherweise jedesmal andere sind !

Tivot aktiv_icon

18:31 Uhr, 04.05.2020

Und das Grundprinzip ist:

Irgendwas mit

n =

Irgendwas mit

n

Also:

Irgendwas mit

n + 1 =

Irgendwas mit

n + 1

Richtig? Oder fehlt mir hier was?

ermanus aktiv_icon

18:33 Uhr, 04.05.2020

Ah! Habe gerade das Video angeschaut. Dort wird mit der Induktionsbehauptung
die Behauptung von (IS) gemeint.
In deinem Aufgabetext wird daher die Induktionsbehauptung gar nicht
verlangt.
Vergiss, was ich zu der Induktionsbehauptung gesagt habe.

ermanus aktiv_icon

18:44 Uhr, 04.05.2020

Ich schreibe dir gleich nochmal die Lösung der gegebenen
Aufgabe so auf, wie ich es machen würde.

Übrigens muss die Aussage, die man beweisen soll/will
nicht die Form einer Gleichung haben und es muss auch nicht zwei Seiten geben
und wenn, muss auch nicht das

n

auf beiden Seiten auftauchen.

Vielmehr will man irgendeine Aussage

A (n)

, die von

n

abhängt
für alle nat. Zahlen

n

beweisen.

IA: Beim Induktionsanfang prüft man die Richtigekeit von

A (n_{0})

für die kleineste nat. Zahl

n_{0}

, für die die Behauptung gelten soll,
meist ist

n_{0} = 0

oder

n_{0} = 1

.

IV: In der Induktionsannahme nimmt man an, dass die Aussage

A (n)

für
ein

n \geq n_{0}

gilt.

IS: hier beweist man

A (n) \Rightarrow A (n + 1)

.

Das ist das Prinzip.

Tivot aktiv_icon

19:13 Uhr, 04.05.2020

Ich habe zu dem Ganzen eine weitere Frage. Mir ist eine sehr einfache Lösung eingefallen. Die Aufgabe war ja:

Es ist zu zeigen, dass:

S (n) = 2^{n - 1}

Prüfen mit

n = 1

(IA)

S (1) = 1,

stimmt (da

2^{1 - 1} = 1)

Induktionsschritt, indem wir einfach

+ 1

auf beiden Seiten zu

n

addieren:

S (n + 1) = 2^{n + 1 - 1}

Stimmt (mit

n = 1,

ist auf beiden Seiten

2)

.

Ist damit die Aufgabe nun gelöst? Ich bin etwas verwirrt, weil nun nirgendwo mehr

2 \cdot S (n)

auftaucht. Was ist da passiert?

ermanus aktiv_icon

19:23 Uhr, 04.05.2020

Auf diese Weise kannst du wohl fast jede, auch noch so falsche Aussage
beweisen.
Es geht bei

A (n) \to A (n + 1)

nicht darum überall

n

einfach durch

n + 1

zu ersetzen,
sondern zu beweisen, dass aus

A (n)

die Aussage

A (n + 1)

folgt.

Nimm als abschreckendes Beipiel die Aussage
"Für alle nat. Zahlen

n \geq 0

gilt

n^{2} = n

."
Der Induktionsanfang ist OK.
Die (IV) wäre: sei für ein

n \geq 0

bereits gezeigt, dass

n^{2} = n

.
So wie du gerade vorgegangen bist, wäre dann ja auch

(n + 1)^{2} = n + 1

...
Das wirst du hoffentlich nicht glauben ;-)

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1501327

1501213

	Status: nicht eingeloggt	Noch nicht registriert?