Beweis mit vollständiger Induktion

01.02.2010, 15:41

fhuchler

Auf diesen Beitrag antworten »

Beweis mit vollständiger Induktion

Hallo zusammen,

ich habe eine Formel die lautet y=k²+(k-1)
Diese Formel sollte ich nun beweisen.

Einschränkung ist: für k dürfen nur positive gerade Zahlen eingesetzt werden. Also 2,4,6,....

Als Induktionsannahme gehe ich davon aus, dass die Formel für k=4 giltet (das habe ich nachgewiesen). Meine Behaupt wäre nun: wenn die Formel für k giltet, muss sie auch für k+2 gelten.

Dann setzte ich das ein und erhalte
k²+5k+5

Mir ist klar dass ich nun irgendwie von der ursprünglichen Formel auf
die berechnete Formel kommen muss, um den Induktionsschritt zu Vollziehen. Und das sollte ich herbekommen wenn ich es schaffe in den Fall für k+2 die bewiesen Formel einzusetzen.
Das will mir aber nicht gelingen. Ich habe den Workshop schon gesehen, da stehen aber nur Beispiel mit Summe und alle mit n+1...ich bräuchte da aber etwas mit n+2...

Jemand von euch eine Idee? Ich hab das Gefühl dass das nicht viel ist und ich da irgendwie davor steh und die Lösung nicht sehe....

Danke & Gruß
Florian

01.02.2010, 15:51

kühlkiste

Auf diesen Beitrag antworten »

RE: Beweis mit vollständiger Induktion

Zitat:

Original von fhuchler
Hallo zusammen,

ich habe eine Formel die lautet y=k²+(k-1)
Diese Formel sollte ich nun beweisen.

Was solls da zu beweisen geben?
Du wirst schon noch was über das y in Deiner Formel erzählen müssen bevor Du da irgendeine Hilfe erwarten darfst.

01.02.2010, 15:58

WebFritzi

Auf diesen Beitrag antworten »

Ich habe auch eine Formel:

$\begin{eqnarray*} \pi\cdot y = 8j^2 - \ln(r) + 555s - \Gamma(x). \end{eqnarray*}$

Kannst du mir die auch per vollst. Induktion beweisen, bitte? Augenzwinkern

Augenzwinkern

01.02.2010, 15:59

fhuchler

Auf diesen Beitrag antworten »

RE: Beweis mit vollständiger Induktion
Hm,....also die Formel dient zu Berechnung einer Schrittanzahl die durch eine Simulator errechnet wird. Und ich möchte jetzt eigentlich zeigen dass diese Formel allgemein gültig ist. Also was immer ich für k-Werte wähle es immer das richtige y rauskommt... verwirrt

verwirrt

Also für k=4 lässt sich der Wert dann einfach ausrechnen...und ich weiß auch schon dass die Formel für alle anderen geraden Zahlen stimmt (da bin ich mir auch ohne korrekten Beweis sicher).

01.02.2010, 16:01

WebFritzi

Auf diesen Beitrag antworten »

Und woher sollen wir das wissen??? unglücklich

unglücklich

01.02.2010, 16:03

fhuchler

Auf diesen Beitrag antworten »

Sorry, ich dachte nicht dass das eigentliche Problem für die Formel relevant ist.

Anzeige

01.02.2010, 16:10

WebFritzi

Auf diesen Beitrag antworten »

Lol... Wenn Formel und Problem voneinander unabhängig wären, dann könntest du doch jede Formel dahernehmen...

Beschreibe den Vorgang also genauer.

01.02.2010, 17:11

fhuchler

Auf diesen Beitrag antworten »

Also dann genau Freude

Freude

=================================
gegeben ist ein Netzwerk der Größe k mit k*k Knoten. Das Netzwerk wird von einem Agent der immer beim Knoten 0/0 startet, durchlaufen. Jeder Knoten im Netzwerk hat einen Zählerstand. Der Agent bewegt sich durch das Netzwerk gem. folgender Regel: als Nachbarknoten wird der Knoten mit dem kleinsten Zählerstand selektiert (kleiner wie der des aktuellen Knotens). Beistzt kein Nachbar einen kleinsten Zählerstand , dann ist einer per Zufall zu selektieren. Der Agent wechselt zu dem Knoten und erhöt dessen Zählerstand. Die Knoten sind über Kanten miteinander verbunden und ein Knoten besitzt maximal vier Kanten. Schlaufen exisitieren nicht. Beispielnetzwerk für k=3:

1 - 1 - 0
| | |
1 - 1 - 1
| | |
1 - 1 - 1

Betrachte man diese Problem mit einer deterministischten Entscheidungsregel für den Agenten (also das er seine nachbarn in einer Reihenfolge durchprobiert: oben, rechts, unten, links), dann stellt man fest, das je nach verwendeter Richtungsreihenfolge eine eindeutige Formel möglich ist. Ich habe als Regelset oben-links-unten-rechts verwendet und bin dann auf die Formel k=k²+(k-1) für gerade Netzwerke (also k=gerade) gestoßen. Mit der Formel wird berechnet wieviel Schritte der Agent im Netzwerk machen muss, um zurück zu seinem Startknoten zu kommen. Für ungerade Netzwerke lautet die Formel y=k²+(2k-2)
=================================

01.02.2010, 17:13

fhuchler

Auf diesen Beitrag antworten »

Zitat:

Original von fhuchler
Also dann genau Freude

Freude

=================================
gegeben ist ein Netzwerk der Größe k mit k*k Knoten. Das Netzwerk wird von einem Agent der immer beim Knoten 0/0 startet, durchlaufen. Jeder Knoten im Netzwerk hat einen Zählerstand. Der Agent bewegt sich durch das Netzwerk gem. folgender Regel: als Nachbarknoten wird der Knoten mit dem kleinsten Zählerstand selektiert (kleiner wie der des aktuellen Knotens). Beistzt kein Nachbar einen kleinsten Zählerstand , dann ist einer per Zufall zu selektieren. Der Agent wechselt zu dem Knoten und erhöt dessen Zählerstand. Die Knoten sind über Kanten miteinander verbunden und ein Knoten besitzt maximal vier Kanten. Schlaufen exisitieren nicht. Beispielnetzwerk für k=3 (nur die Zählerstände an der jeweiligen Netzwerkposition, die senkrechten Kanten lass ich weg, die werden nur verschoben dargestellt)

1 - 1 - 0
1 - 1 - 1
1 - 1 - 1

Betrachte man diese Problem mit einer deterministischten Entscheidungsregel für den Agenten (also das er seine nachbarn in einer Reihenfolge durchprobiert: oben, rechts, unten, links), dann stellt man fest, das je nach verwendeter Richtungsreihenfolge eine eindeutige Formel möglich ist. Ich habe als Regelset oben-links-unten-rechts verwendet und bin dann auf die Formel k=k²+(k-1) für gerade Netzwerke (also k=gerade) gestoßen. Mit der Formel wird berechnet wieviel Schritte der Agent im Netzwerk machen muss, um zurück zu seinem Startknoten zu kommen. Für ungerade Netzwerke lautet die Formel y=k²+(2k-2)
=================================

01.02.2010, 17:51

JohannesW

Auf diesen Beitrag antworten »

Hallo, du hast hier eine Folge die du beweisen und dafür brauchst du die rekursive Bildungsvorschrift:

$\begin{eqnarray*} y_{2}=?, y_{k+2}=y_{k}+x(k) \end{eqnarray*}$

Der Wert x ist die Anzahl der Schritte die du zusätzlich brauchst, wenn du dein k um 2 erhöhst. Dieses x ist von k abhängig.

Diese x mußt du finden und dann nachweisen, dass es sich tatsächlich immer um diesen Wert handelt.

Anschließend kannst du mit vollständiger Induktion deine Formel beweisen.

01.02.2010, 21:10

fhuchler

Auf diesen Beitrag antworten »

Hallo JohannesW,

vielen Dank für deinen Tip.
Ich hab mir das angesehen und bin auf folgendes Ergebnis gekommen:

$\begin{eqnarray*} <br /> y(2)=5 (vordefiniert)<br /> y_{k+2} = y_{k} + 4*(k+2) - 2<br /> \end{eqnarray*}$

Jetzt habe ich schon mal die Folge mit der sich die Schrittanzahl berechnen lässt.
Jetzt zeige ich das diese Folge zuerst mal für ein y gilt. also wähle ich k=2 und berechne damit den wert für y(4):

$\begin{eqnarray*} y_{4}= 5 + 4*4 - 2 = 19 \end{eqnarray*}$

Das stimmt auch so (also wenn man
$\begin{eqnarray*} k^{2}+(k-1) \end{eqnarray*}$
rechnet kommt man auf dasselbe Ergebnis).

Jetzt ist die Induktionsannahme, dass wenn die Folge für k giltet, diese auch für k+2 giltet. Also setzte ich k+2 ein:
$\begin{eqnarray*} <br /> y_{k+2+2} = y_{k+2}+4*(k+2+2)-2<br /> <br /> y_{k+4} = y_{k+2} + 4*(k+4) -2<br /> <br /> \end{eqnarray*}$

So, und da weiß ich jetzt nicht weiter. Da müsste ich jetzt doch für den rechten ausdruck mit
$\begin{eqnarray*} y_{k+2} \end{eqnarray*}$
meine Induktionsannahmeformel einsetzen, oder?

02.02.2010, 00:02

JohannesW

Auf diesen Beitrag antworten »

Es geht bei dem Beweis nicht um die Folge, dass die Folge gilt, mußt du anhand deines Netzes logisch folgern.

Hier mußt du erst zeigen, dass deine Formel für das erste y gilt, hier $\begin{eqnarray*} y_{2} \end{eqnarray*}$ .

D.h.: Induktionsvoraussetzung:

$\begin{eqnarray*} y_{k} = deine-Formel \end{eqnarray*}$

und Induktionsannahme:
$\begin{eqnarray*} y_{k+2} =deine-Formel-mit-'k+2' \end{eqnarray*}$

Jetzt folgt noch der Beweis, dass es wirklich so ist und dazu brauchst du die rekursive Folge.

PS: wenn du für k=2n einsetzt erhältst du die ganz normale vollständige Induktion mit n und n+1. Ähnlich kannst du es auch für ungerade machen.

LG

Johannes

02.02.2010, 13:31

fhuchler

Auf diesen Beitrag antworten »

Hallo JohannesW

nochmals vielen Dank vorweg für deine Hilfe. Ist schon ein paar Jahre her dass ich das gerlent hatte.

Ich probier dass jetzt mal:

Davon ausgehende, dass ich nachgewiesen habe, dass die Folge für
$\begin{eqnarray*} y_{k+2}=y_{k}+4(k+2)-2 \end{eqnarray*}$
gültig ist, würde ich nun wie folgt weiter vorgehen.

Meine IV ist, dass die Formel
$\begin{eqnarray*} y_{k}=k^{2}+(k-1) \end{eqnarray*}$
gültig ist. Ich weiße das nach in dem ich den Fall für k=2 und k=4 konstruiere und dass grafische belege dass für diese beiden k die Aussage stimmt.

Meine Induktionsannahme ist nun, dass die Formel auch für alle
$\begin{eqnarray*} y_{k+2} \end{eqnarray*}$
giltet.

Also rechne ich den Fall mit
$\begin{eqnarray*} y_{k+2} \end{eqnarray*}$
durch, d.h. ich setze in meine "angenommenen" korrekte Formel k²+(k-1) für k = k+2 ein.

$\begin{eqnarray*} <br /> y_{k+2} = (k+2)^{2}+(k+2-1)<br /> y_{k+2} = k^{2}+4k+4+k+1<br /> y_{k+2} = k^{2}+5k+5<br /> \end{eqnarray*}$

Nun prüfe ich ob die Folge zum selben Ergebnis kommt.
Laut IV ist die Formel für k gültig, also kann ich für y_k = k²+(k-1) einsetzen

$\begin{eqnarray*} <br /> y_{k+2} = y_{k}+4(k+2)-2<br /> y_{k+2} = k^{2}+(k-1)+4(k+2)-2<br /> y_{k+2} = k^{2}+k-1+4k+8-2<br /> y_{k+2} = k^{2}+5k+5<br /> \end{eqnarray*}$

Offensichtlich ist die Aussage richtig.
Passt das so oder mus sich da noch mehr rein machen?

02.02.2010, 18:29

JohannesW

Auf diesen Beitrag antworten »

Ja, das passt so, ich würd aber beim letzten Teil die Reihenfolge umdrehen:

$\begin{eqnarray*} y_{k+2} = k^{2}+5k+5 \end{eqnarray*}$
$\begin{eqnarray*} y_{k+2} = k^{2}+(k-1)+4k+6 \end{eqnarray*}$
$\begin{eqnarray*} y_{k+2} = y_{k}+4k+8-2 \end{eqnarray*}$
$\begin{eqnarray*} y_{k+2} = y_{k}+4(k+2)-2 \end{eqnarray*}$

Wenn du die Kette so drehst nimmst du als Ausgangspunkt deine Formel und zeigst, dass sie das gleiche besagt wie die Folge. Sieht einfach für Mathematiker so schöner aus. Augenzwinkern

Augenzwinkern

08.03.2010, 20:12

fhuchler

Auf diesen Beitrag antworten »

Hallo Mathegemeinde,

ich bin's nochmals mit Vollständiger Induktion...das will einfach nicht so wie ich will.

Es geht um das bereits oben angeführten Problem.
Ich habe inzwischen eine Formel für die Ermittlung eines maximalen Wegs in meinem Netzwerk hergeleitet, die scheint zu stimmen, ich konnte das Ergebnis für k=2 und k=4 verifizieren. Aber mir fehlt der Beweis und die Formel gilt nur für ganze gerade Zahlen.

Die Formel lautet:
$\begin{eqnarray*} S_{max} =\sum\limits_{i=0}^{2k-3} (k^2-i) \end{eqnarray*}$

Mein IA wäre jetzt zu zeigen dass die Formel für k=2 gilt. Da kann ich an Hand eines Beispiels machen.

Dann hätte ich die Induktionsvoraussetzung IV beschrieben, nämlich dass wir Annehmen, dass die Formel für Werte von {2,...k} gilt. Im Induktionsschluss wollte ich nun zeigen, dass die Formel auch für k+2 gilt, also {2,...k}+k+2. Dann kann/muss/darf ich annehmen, dass Aufgrund der IV die Formel für {2,...k} gilt. Also addiere ich da nochmals ((k+2)²-i) dazu.

$\begin{eqnarray*} S_{max} =\sum\limits_{i=0}^{2k-3} (k^2-i) + (({k+2)}^2-i) \end{eqnarray*}$

Nach ein wenig umstellen komme ich dann auf

$\begin{eqnarray*} S_{max} =\sum\limits_{i=0}^{2k-2} (k^2-i) + 4k+4 \end{eqnarray*}$

Setze ich nun umgekehrt (k+2) in die Ausgangsformel (die ich beweisen möchte) ein, dann müsste doch dasselbe herauskommen wie gerade eben.

$\begin{eqnarray*} S_{max} =\sum\limits_{i=0}^{2(k+2)-3} ((k+2)^2-i) \end{eqnarray*}$

Mit Umformen komme ich da nun aber auf

$\begin{eqnarray*} S_{max} =\sum\limits_{i=0}^{2k+1} (k^2-i) +4k+4 \end{eqnarray*}$

Mein Wert über dem Summenzeichen passt einfach nicht.

Zwei Fragen dazu
a) Mach ich das so richtig? Wenn nicht - kann mich jemand auf den richtigen Pfad geleiten?
b) Hat jemand eine Idee wo mein Fehler liegt?

Danke für eure Ratschläge.

Gruß

09.03.2010, 15:31

fhuchler

Auf diesen Beitrag antworten »

*thema nach oben hol*

22.03.2010, 07:36

JohannesW

Auf diesen Beitrag antworten »

Hi, was du beweisen willst ist ja:

$\begin{eqnarray*} S_{k_{max}}=\sum\limits_{i=0}^{2k-3}(k^{2}-i) \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow S_{k+2_{max}}=S_{k_{max}}+a_{k+2_{max}}=\sum\limits_{i=0}^{2k-3}(k^{2}-i)+a_{k+2_{max}}=\sum\limits_{i=0}^{2(k+2)-3}((k+2)^{2}-i) \end{eqnarray*}$

Jetzt müßtest du $\begin{eqnarray*} a_{k+2_{max}} \end{eqnarray*}$ bestimmen, $\begin{eqnarray*} a_{k+2_{max}} \end{eqnarray*}$ darf allerdings nur von k, nicht von i abhängig sein und dann zeigen, dass die Formel stimmt.

LG

Johannes

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »