Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Starke Induktion

Starke Induktion

Universität / Fachhochschule

Sonstiges

Tags: Sonstiges

iri18 aktiv_icon

12:26 Uhr, 05.01.2011

mittels starker Induktion soll man beweisen: Für alle

n

element aus den natürlichen Zahlen (mit

0)

f (n) = 2

hoch

n - 1

iri18 aktiv_icon

13:28 Uhr, 05.01.2011

was heißt starke induktion?

i

weiß dass man bei einer normalen vollständigen induktion zuerst den induktionsbeginn beweist ( also

n = 1)

und dann den induktionsschritt

(P (n) \Rightarrow P (n + 1))

aber wie mach ich das bei einer starken induktion???

michaL aktiv_icon

13:36 Uhr, 05.01.2011

Hallo,

ich habe weniger ein Problem mit starker Induktion denn mit der Fragestellung überhaupt. Was soll man denn überhaupt zeigen?
Offenbar solltest du entweder die Originalaufgabenstellung gleich mitposten (erspart Zeit) oder lernen, wie man seine Fragen so stellt, dass Rückfragen unwahrscheinlich sind.

Mfg MIchael

PS: Bei der starken Induktion darf man (meines Wissens) annehmen, dass die zu beweisende Aussage

A (n)

für alle

n \leq n_{0}

gilt, wenn man

A (n_{0} + 1)

beweisen will.

iri18 aktiv_icon

13:45 Uhr, 05.01.2011

Also:

Sei

f

eine Funktion: Natürliche Zahlen( mit

0)

nach

R

(Reellen Zahlen) gegeben durch die rekursive Definition

f (0) = 0

f (1) = 1

f (n + 1) = 3 f (n) - 2 f (n - 1)

für

n

größer gleich 1

Beweise mittels starker Induktion: Für alle

n

Element aus den natürlichen Zahlen (mit

0)

gilt:

f (n) = (2

hoch

n) - 1

iri18 aktiv_icon

14:03 Uhr, 05.01.2011

sagt dir das jez etwas????

michaL aktiv_icon

14:09 Uhr, 05.01.2011

Hallo,

ok, du musst als Induktionsanfang die Formel für

n = 0

und

n = 1

nachweisen.
Als Induktionsschritt musst du beweisen, dass

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

gilt. Kriegst du das hin?

Mfg Michael

iri18 aktiv_icon

14:11 Uhr, 05.01.2011

ok das ist schon mal super hilfreich aber bei einer starken induktion braucht man ja garkeinen induktionsbeginn oda??? :-)

michaL aktiv_icon

14:17 Uhr, 05.01.2011

Hallo,

doch, braucht man da auch. Die selbe Formel wird doch sicher nicht gelten, wenn du

f (0) := 1

und

f (1) := 2

wählst, oder?

Mfg Michael

iri18 aktiv_icon

14:23 Uhr, 05.01.2011

bei mir kommt hinaus:

(4

hoch

n) - 1 = (4

hoch

n) - 1

schaut gut aus oda?

michaL aktiv_icon

14:32 Uhr, 05.01.2011

Hallo,

wenn das beim Induktionsende ist, dann ja!

Mfg Michael

iri18 aktiv_icon

14:33 Uhr, 05.01.2011

ja das war bei

f (n + 1) ...

ich denke ich bin dann mit dem beispiel fertig oda? :-D)
DANKE fürs helfen..
studierst du selbst mathe oder was machst du?

michaL aktiv_icon

14:57 Uhr, 05.01.2011

Hallo,

wenn du den Induktionsanfang wie beschrieben gemacht hast, solltest du fertig sein.
Ich studiere nicht mehr, ich hab einen Abschluss. Ich bin mittlerweile Mathelehrer in Niedersachsen. Naja, hab ja auch auf Lehramt studiert...

Mfg Michael

iri18 aktiv_icon

15:33 Uhr, 05.01.2011

aso

⊙ k

super danke!
habe jetzt keinen induktionsanfang gemacht weil ich ja bei der Angabe steht:

f (o) = 0

und

f (1) = 1

das wäre ja dasselbe wie wenn ich jez schreibe

n = 0 \Rightarrow f (o) = 0

n = 1 \Rightarrow f (1) = 1

aber wiegesagt bei dem induktionsschritt kommt eine wahre aussage heraus :-)

hagman aktiv_icon

15:38 Uhr, 07.01.2011

Es ist trotrzdem erforderlich, hinzuschreiben, dass die Aussage für

n = 0

und

n = 1

die Aussage (von mir aus trivialerweise) gilt, den der Induktionsschritt kann ja nur Aussagen über

f (n)

mit

n \geq 2

machen:

f (0) = 0 = 2^{0} - 1

und

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

gilt unmittelbar nach Definition von

f

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

838655

837681

	Status: nicht eingeloggt	Noch nicht registriert?