Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Induktion - Rekursive Folge <--> geschlossene Form

Induktion - Rekursive Folge <--> geschlossene Form

Universität / Fachhochschule

Folgen und Reihen

Funktionen

Funktionenfolgen

Tags: Folgen und Reihen, Funktion, Funktionenfolgen, Induktion, Vollständig Induktion

AngelsEnd aktiv_icon

15:58 Uhr, 27.04.2017

Hallo,

ich habe zu folgenden 2 Aufgaben eine Frage. Und zwar würde ich gerne von euch wissen, ob mein Vorgehene anhand der vollständigen Induktion hier so passt/korrekt ist. Ist mein Beweis vollständig oder habe ich noch ein Schritt/Schritte vergessen?

Gegeben folgende rekursive Form:

T (n) = T (n - 2) + 2 * n

Es darf angenommen werden, dass n gerade und es gilt für n = 0 T(0) = 0

Finden einer geschlossenen Form und beweisen der Korrektheit mittels Vollständiger Induktion.

Ich habe folgende geschlossene Form gefunden

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

Induktionsanfang: n = 0 -> T(0)

=_{d e f} 0 = (\frac{0}{2} + 1) * 0 = > 0 = 0

passt

Induktionsvoraussetzung: T(n) = f(n) gilt für

n \in ℕ

Induktionsbehauptung: Dann gilt die Vermutung auch für n + 1

Beweis:

T (n + 1) =_{d e f} T ([n + 1] - 2) + 2 (n + 1) = (\frac{n + 1}{2} + 1) * (n + 1)

= \frac{n + 1 + 2}{2} * (n + 1) = \frac{(n + 1 + 2) * (n + 1)}{2} = \frac{n^{2} + n + n + 1 + 2 n + 2}{2} = \frac{n^{2} + 4 n + 2 + 1}{2} = \frac{(n + 1)^{2} + 1}{2} = \frac{(n + 1) + 1}{2} * (n + 1)

Fertig!

Die 2. Aufgabe wäre:

T (n) = 8 * T (\frac{n}{2}) + n^{2}

man darf annehmen, das n eine Zweierpotenz ist und es gilt T(1) = 1

Ich habe die geschlossene Form

f (n) = 4^{n - 1} * (2^{n} - 1)

gefunden und will dies nun durch vollständige Induktion beweisen

Induktionsanfang: n = 1 -> T(1)

=_{d e f} 1 = 4^{1 - 1} * (2^{1} - 1) = > 1 = 1

passt

Induktionsvoraussetzung: T(n) = f(n) gilt für

n \in ℕ

Induktionsbehauptung: Dann gilt die Vermutung auch für n + 1

Beweis:

T (n + 1) =_{d e f} 8 * T (\frac{n + 1}{2}) + (n + 1)^{2} = 4^{(n + 1) - 1} * (2^{n + 1} - 1) = 4^{n} * (2^{n + 1} - 1)

Fertig?

Nun die Frage an euch, stimmt das so oder habe ich irgendwo Denkfehler bzw. etwas vergessen?

Gruß

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

Hierzu passend bei OnlineMathe:
Funktion (Mathematischer Grundbegriff)

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Einführung Funktionen

rundblick aktiv_icon

16:31 Uhr, 27.04.2017

.

"T(n)=T(n−2)+2∗n Es darf angenommen werden, dass

n

gerade .."

. .

\leftarrow . .

!! .

\to

hast du die Aufgabe denn gelesen ??

1) \to

"Ich habe folgende geschlossene Form gefunden

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

... < .

. JA, für welche n?

2) \to

"Induktionsvoraussetzung:

T (n) = f (n)

gilt für

\to

n∈ℕ "

... . . < .

. NEIN !

also denke ganz neu nochmal besser nach

. .

.

nebenbei:
das, was du freudig vor deinem "Fertig !" stehen hast , ist besonders schön falsch :

dies

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

aua..

AngelsEnd aktiv_icon

17:37 Uhr, 27.04.2017

Darum habe ich die Frage hier gepostet, weil ich in Dingen Mathe und Induktion nicht sonderlich weit komme

Jep da is mir ein Fehler passiert. Wie verfahre ich dann nach

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

weiter?

Vollständige Induktion war noch nie mein Ding.

Ich dachte halt, n = gerade gilt nur als Annahme für die Rekursive Form und hat für die geschlossene Form keine Relevanz. Es kommt nämlich für die ersten ca 10 Werte sowohl für rekursive als auch geschlossene Form das gleiche raus. Wäre also ebenfalls spitze, wenn du deine Bedenken konkretisieren könntest!

PS: Wenn ich mir deine restlichen Antworten hier im Forum so durchlese, scheint deine unhöfliche und (meiner Meinung nach) beleidigende Art wohl an der Tagesordnung zu liegen. Na dann... mach weiter so *thumbs up*

ledum aktiv_icon

19:49 Uhr, 27.04.2017

Hallo
auch wenn

V . I

. nicht dein Ding ist, du solltest wissen, dass man aus der Annahme dass die Formel für

n

richtig ist herleiten muss, dass sie für

n + 1

(hier für

n + 2

richtig ist).

n

Ungerade? wie willst du aus

T (0)

denn

T (1)

ausrechnen, wie Aus

T (n) T (n + 1)

deshalb die geraden Zahlen
wie kommst du auf die Gleichung in der =_def steht die Definitionsgleichung ist doch die Rekursionsgleichung?
hallo also schreib: für

n

gerade gilt:

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

daraus

T (n + 2) =

Rekursionsgleichung, und daraus dann die Formel herleiten.
Wenn dir das Forum nicht passt, musst du es nicht benutzen. Wenn du genauer liest siehst du vielleicht wieviel freiwillige unbezahlte Arbeit hier drin hängt, und wenn Fragende erwachsen sind sollten sie ein bissel Ironie verstehen, wir beklagen uns ja auch nicht , wenn wir dir bei was helfen was nicht dein Ding ist.
ich habe mir

r' s

post angesehen , was daran ist denn unhöflich? das aua?
Wenn du Nachhilfe gäbst und den

S

sagt

3 \cdot 7 = 27

wie reagierst du dann? wie würde er auf aua reagieren?

AngelsEnd aktiv_icon

22:15 Uhr, 27.04.2017

Ah ok, glaube dann verstehe ich das langsam mit dem Annahme n ist gerade.

Aber sollte es dann nicht anstelle von n+2 eher 2n heißen? weil n+2 kann wieder ungerade sein. Oder habe ich immer noch einen Beobachtungsfehler?

ledum aktiv_icon

22:55 Uhr, 28.04.2017

Hallo wenn du mit

n = 0

anfängst und immer

+ 2

weiter gehst, erreichst du doch immer die nächste gerade Zahl. anderer Weg, nenne

n = 2 m

und gehe mit

m

immer 1 weiter.
Gruß ledum

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

1367692

1367460

	Status: nicht eingeloggt	Noch nicht registriert?