Explizite Formel Induktionsbew < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:16 Do 21.11.2013 | | Autor: | lapeiluw |
Hallo zusammen,
ich sitze seit 2 Tagen an einer Aufgabe. Und zwar geht es um folgendes:
| Aufgabe | Sei f: N-->N rekursiv definiert durch f(n+2)=2f(n+1)-f(n). Finde geschlossene Ausdrücke (explizite) für fn, falls
a) f1=1, f2=2
b) f1=1, f2=3
Beweise Gültigkeit mittels vollständiger Induktion. |
Also die expliziten Ausdrücke habe ich für a) und b) gefunden.
a) f(n)=n und b) f(n)=2n-1
Nun zu meinem Problem, diese ausdrücke per vollständiger Induktion zu beweisen. Ich habe mit a) angefangen, hänge jedoch. Ich notiere alles, was ich habe:
Induktionsbehauptung: f(n)=n
Induktionsanfang: n=1, das hieße f(1)=1, das stimmt mit der Vorgabe überein, da ja bereits in der Aufgabe f1=1 gegeben wird.
Induktionsvoraussetzung: für n sei dies wahr und kann weiter genutzt werden.
Induktionsschritt: n --> n+1, d.h. f(n+1)=n+1 ist zu zeigen
nun, wie gehe ich vor, wenn ich eine Rekursionsvorschrift habe, die ja 3 aufeinanderfolgende Glieder enthälft: f(n),f(n+1),f(n+2) und in der rekursiven Vorschrift ist ja f(n+1) definiert, also nicht f(n) !!!
Ich habe also zuerst die rekursive Vorschrift für f(n) umgewandelt:
kommt raus: f(n)=2f(n-1)-f(n-2)
nun setze ich für n --> n+1 ein:
f(n+1)=2f(n+1-1)-f(n+1-2)
fasse zusammen: f(n+1)=2f(n)-f(n-1)
für f(n) kann ich nun die Induktionsvoraussetzung nutzen, was mache ich jedoch mit f(n-1)?????
das heißt ich komme nur bis:
f(n+1)=2n-f(n-1), ich habe ja nix gegeben, wie ich f(n-1) ersetzen könnte... tja, da stehe ich nun, und frage mich, wie das weiter zu machen ist, wenn man in der rekursiven vorschrift nicht nur n und n+1 hat sondern auch n+2.
Vielen Dank für jegliche Denkanstöße, zu b) bin ich noch gar nicht gekommen, da ja dort das vorgehen ähnlich ist. das Problem ist dort das gleiche.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:17 Do 21.11.2013 | | Autor: | lapeiluw |
in der rekursiven Formel ist natürlich f(n+2) und nicht f(n+1) definiert. Tippfehler!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 Do 21.11.2013 | | Autor: | Ebri |
Du kannst deinen Beitrag bearbeiten.
Reagieren -> Als Autor,.. bearbeiten.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:42 Do 21.11.2013 | | Autor: | Ebri |
> Hallo zusammen,
>
> ich sitze seit 2 Tagen an einer Aufgabe. Und zwar geht es
> um folgendes:
>
> Sei f: N-->N rekursiv definiert durch f(n+2)=2f(n+1)-f(n).
> Finde geschlossene Ausdrücke (explizite) für fn, falls
> a) f1=1, f2=2
> b) f1=1, f2=3
>
> Beweise Gültigkeit mittels vollständiger Induktion.
> Also die expliziten Ausdrücke habe ich für a) und b)
> gefunden.
>
> a) f(n)=n und b) f(n)=2n-1
>
> Nun zu meinem Problem, diese ausdrücke per vollständiger
> Induktion zu beweisen. Ich habe mit a) angefangen, hänge
> jedoch. Ich notiere alles, was ich habe:
>
> Induktionsbehauptung: f(n)=n
> Induktionsanfang: n=1, das hieße f(1)=1, das stimmt mit
Nein.
Für den Induktionsanfang n=1 muss man hier Zeigen f(1+2)=f(3)=3
> der Vorgabe überein, da ja bereits in der Aufgabe f1=1
> gegeben wird.
> Induktionsvoraussetzung: für n sei dies wahr und kann
> weiter genutzt werden.
>
> Induktionsschritt: n --> n+1, d.h. f(n+1)=n+1 ist zu
> zeigen
Auch nicht richtig.
n -> n+1 d.h. f(n+2) -> f((n+1)+2)
Also ist zur zeigen: f((n+1)+2) = f(n+3) = n+3
f((n+1)+2) = 2f((n+1)+1)-f(n+1) ... hier kommt die Induktionsvoraussetzung ins Spiel
Gruß
Ebri
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:43 Do 21.11.2013 | | Autor: | lapeiluw |
oh ok, danke für die Hinweise. Ich versuche hier eine Lösung, so wie es mir jetzt nach deinen Hinweisen richtig erscheint:
für a) I-anfang: n=1, f(n+2) --> f(1+2)=f(3)
(lt. expliziter Formel) f(n)=n --> f(3)=3
(lt. rekursiver Formel) f(3)= 2f(1+1)-f(1)=2*f(2)-f(1)=2*2-1=3
stimmt also!
I-Schritt: n--> n+1, d.h. f(n+2)--> f((n+1)+2)
f((n+1)+2)=f(n+3)=n+3 ist zu zeigen
f(n+3)=2*f((n+1)+1)-f(n+1)=2*f(n+2)-f(n+1)= jetzt wirds spannend, darf ich für f(n+2)=n+2 und f+r f(n+1)=n+1 voraussetzen und benutzen? wenn ja, dann folgt:
=2*(n+2)-(n+1)=2*n+4-n-1=n+n+4-n-1=n+n-n+4-1=n+3
damit bewiesen.
b) Anfang: n=1 --> f(n+2)=f(1+2)=f(3)
(lt. expliziter) f(n)=2*n-1 --> f(3)=2*3-1=5
(lt. rekursiver) f(1+2)=2*f(1+1)-f(1)=2*f(2)-f(1)=(lt. definition f1 und f2) =2*3-1=5
stimmt!!!
Schritt: n--> n+1, d.h. f(n+2)-->f((n+1)+2)=f(n+3)
f(n+3)=2*(n+3)-1 (explizite F.) =(2n+6)-1=2n+5 das ist zu beweisen
beweis mit rekursiver:
f(n+3)=2*f((n+1)+1)-f(n+1)=2*f(n+2)-f(n+1)= nun wieder die gleiche frage wie oben, darf ich f(n+2)=2*(n+2)-1=2n+3 und f(n+1)=2*(n+1)-1=2n+1 voraussetzen? wenn ja, dann weiter:
f(n+3)=2*(2n+3)-(2n+1)=4n+6-2n-1=2n+5.
damit wäre es bewiesen.
Warum ich mich so schwer tue, ist, da wir bisher immer gesagt haben, als Induktionsvoraussetzung nehme ich die Richtigkeit meiner Behauptung für n an! und hier muss ich es für n+1 und für n+2 annehmen, damit ich n+3 beweisen kann.
Ist es denn so richtig?
Vielen Dank
|
|
|
| |
|
oh ok, danke für die Hinweise. Ich versuche hier eine Lösung, so wie es mir jetzt nach deinen Hinweisen richtig erscheint:
für a) I-anfang: n=1, f(n+2) --> f(1+2)=f(3)
(lt. expliziter Formel) f(n)=n --> f(3)=3
(lt. rekursiver Formel) f(3)= 2f(1+1)-f(1)=2*f(2)-f(1)=2*2-1=3
stimmt also!
I-Schritt: n--> n+1, d.h. f(n+2)--> f((n+1)+2)
f((n+1)+2)=f(n+3)=n+3 ist zu zeigen
f(n+3)=2*f((n+1)+1)-f(n+1)=2*f(n+2)-f(n+1)= jetzt wirds spannend, darf ich für f(n+2)=n+2 und f+r f(n+1)=n+1 voraussetzen und benutzen? wenn ja, dann folgt:
=2*(n+2)-(n+1)=2*n+4-n-1=n+n+4-n-1=n+n-n+4-1=n+3
damit bewiesen.
b) Anfang: n=1 --> f(n+2)=f(1+2)=f(3)
(lt. expliziter) f(n)=2*n-1 --> f(3)=2*3-1=5
(lt. rekursiver) f(1+2)=2*f(1+1)-f(1)=2*f(2)-f(1)=(lt. definition f1 und f2) =2*3-1=5
stimmt!!!
Schritt: n--> n+1, d.h. f(n+2)-->f((n+1)+2)=f(n+3)
f(n+3)=2*(n+3)-1 (explizite F.) =(2n+6)-1=2n+5 das ist zu beweisen
beweis mit rekursiver:
f(n+3)=2*f((n+1)+1)-f(n+1)=2*f(n+2)-f(n+1)= nun wieder die gleiche frage wie oben, darf ich f(n+2)=2*(n+2)-1=2n+3 und f(n+1)=2*(n+1)-1=2n+1 voraussetzen? wenn ja, dann weiter:
f(n+3)=2*(2n+3)-(2n+1)=4n+6-2n-1=2n+5.
damit wäre es bewiesen.
Warum ich mich so schwer tue, ist, da wir bisher immer gesagt haben, als Induktionsvoraussetzung nehme ich die Richtigkeit meiner Behauptung für n an! und hier muss ich es für n+1 und für n+2 annehmen, damit ich n+3 beweisen kann.
Ist es denn so richtig?
Vielen Dank
(entschuldigt, diesen mehrfachen Beitrag, wollte gern eine Frage aus meiner Mitteilung machen, hab es aber nicht geschafft)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:51 Fr 22.11.2013 | | Autor: | Marcel |
Hallo,
ist jetzt nicht böse gemeint, aber würdest Du den Formeleditor benutzen
(https://matheraum.de/mm oder ![[]](/images/popup.gif) http://de.wikipedia.org/wiki/Hilfe:TeX),
würde ich mir mehr Zeit nehmen. Deine Frage ist mir etwas zu unleserlich,
zu so später Uhrzeit macht mich das müde ^^ . Aber ich stelle sie gleich auf
teilweise beantwortet, damit auch andere mehr dazu sagen können...
Eigentlich habe ich nur eine Kleinigkeit anzumerken:
Du hattest
[mm] $f(n+2):=2f(n+1)-f(n)\,$
[/mm]
mit [mm] $f(1):=1\,$ [/mm] und [mm] $f(2):=2\,.$
[/mm]
Du wolltest nun per vollständiger Induktion
[mm] $f(n)=n\,$ [/mm] für alle $n [mm] \in \IN$
[/mm]
begründen.
Hier solltest Du, und das war auch eine Frage, die Du implizit irgendwo
eben gestellt hattest, eine gewisse Variante der  Induktion verwenden:
Feststellung 1.2.10 (klick!)
(Anmerkung: Wir sollten, falls das noch nicht bei uns im Vorwissen-Bereich
irgendwo steht, diese Variante dort auch mal formulieren...)
Diese ist äquivalent zum "normalen" Induktionsprinzip.
Das geht dann so:
Zu zeigen ist, dass [mm] $A(n)\,$ [/mm] für alle $n [mm] \in \IN$ [/mm] wahr ist.
1. Induktionsanfang: Man zeigt, dass [mm] $A(k)\,$ [/mm] für [mm] $k=1,...,n_0$ [/mm] wahr ist (bei Dir ist [mm] $n_0=2\,.$).
[/mm]
2. Sei nun $n [mm] \in \IN$ [/mm] mit $n [mm] \ge n_0\,.$ [/mm] Man will nun im Induktionsschritt zeigen, dass
[mm] $A(n+1)\,$
[/mm]
wahr ist. Als Induktionsannahme/-voraussetzung setzt man nun voraus:
[mm] $A(k)\,$ [/mm] ist wahr für alle [mm] $k=1,...,n\,.$
[/mm]
Ich zeige Dir jetzt, wie das bei Deiner Aufgabe funktioniert (und Du kannst
einfach schnell drüberlesen und mit Deiner Lösung vergleichen, ob sie
damit identisch ist):
Zum Induktionsstart: Für $k=1$ gilt [mm] $f(1)=1\,$ [/mm] und für [mm] $k=2\,$ [/mm] gilt [mm] $f(2)=2\,.$ [/mm]
Induktionsschritt: Wir nehmen nun also $n [mm] \in \IN$ [/mm] mit $n [mm] \;\ge\; [/mm] 2$ an und,
dass
[mm] $f(k)=k\,$ [/mm] für alle $k=1,...,n$
gilt. Dann gilt insbesondere
[mm] $f(n-1)=n-1\,$ [/mm] und [mm] $f(n)=n\,.$
[/mm]
Per Definitionem von [mm] $f\,$ [/mm] gilt
[mm] $f(n+1)=2f(n)-f(n-1)\,,$
[/mm]
und mit der I.V. folgt
[mm] $f(n+1)=2*n-(n-1)=2n-n+1=n+1\,.$
[/mm]
Dies beendet den Beweis. [mm] $\hfill \Box$
[/mm]
Ich finde übrigens den Hinweis, dass Du [mm] $f(3)=3\,$ [/mm] und dann [mm] $f(n+3)=n+3\,$
[/mm]
zeigen sollst, nicht so wirklich gut. Damit unterschlägt man [mm] $f(1)=1\,$ [/mm] und [mm] $f(2)=2\,,$
[/mm]
und zeigt eigentlich nur, dass
[mm] $f(n)=n\,$ [/mm] für alle $n [mm] \ge 3\,$
[/mm]
gilt. Im Induktionsschritt mag das "schöner aussehen" (da man die Formel
dann direkt per Definitionem anwenden kann), aber um wirklich
[mm] $f(n)=n\,$ [/mm] für alle $n [mm] \in \IN$
[/mm]
nachzweisen, müßte man das schon vollständig aufschreiben:
Wir behaupten [mm] $f(n)=n\,$ [/mm] für alle $n [mm] \in \IN.$ [/mm] Für $n=1,2$ ist dies per Definitionem
klar. Es bleibt also noch [mm] $f(m)=m\,$ [/mm] für alle $m [mm] \ge [/mm] 3$ zu beweisen. Dazu schreiben
wir [mm] $m=n+2\,$ [/mm] - dann durchläuft [mm] $m\,$ [/mm] die Zahlen $3,4,5,...$ so, wie [mm] $n\,$ [/mm] halt $1,2,3,...$
durchläuft.
Für [mm] $n=1\,$ [/mm] bzw. [mm] $m=3\,$ [/mm] gilt
[mm] $f(1+2)=f(3)=f(m)=2*f(2)-f(1)=2*2-1=4-1=3=m=n+1\,.$
[/mm]
$n [mm] \to [/mm] n+1$ [mm] ($\iff$ [/mm] $m [mm] \to [/mm] m+1$):
Gelte also $f(k+2)=k+2$ für alle $k=1,...,n$ (also [mm] $f(\ell)=\ell\,$ [/mm] für alle [mm] $\ell=3,...,m=n+2$)
[/mm]
$f((n+1)+2)=f(m+1)=f(n+3)=2*f(n+2)-f(n+1)=2*f(m)-f(m-1)$
Und jetzt sieht man den Haken bei dieser Methode: Wäre bei der Aufgabe
nicht [mm] $f(2)=2\,$ [/mm] gewesen, geht hier alles schief. Im Induktionsbeweis muss
man auch aufpassen:
Wenn [mm] $n=1\,$ [/mm] bzw. [mm] $m=3\,$ [/mm] ist, taucht der Terminus [mm] $f(n+1)=f(2)=f(m-1)\,$ [/mm] auf. Über
den wird aber hier - bei dieser Art des Induktionsbeweises, so, wie er von
Ebri hier (klick!) vorgeschlagen wurde, gar keine Aussage mehr im
Induktionsschritt gemacht.
Mit anderen Worten: Diese Methode kann "gefährlich" werden, wenn man
dabei nicht den kompletten Überblick behält.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:17 Fr 22.11.2013 | | Autor: | Marcel |
Hallo,
> oh ok, danke für die Hinweise. Ich versuche hier eine
> Lösung, so wie es mir jetzt nach deinen Hinweisen richtig
> erscheint:
>
> für a) I-anfang: n=1, f(n+2) --> f(1+2)=f(3)
> (lt. expliziter Formel) f(n)=n --> f(3)=3
> (lt. rekursiver Formel) f(3)=
> 2f(1+1)-f(1)=2*f(2)-f(1)=2*2-1=3
> stimmt also!
>
> I-Schritt: n--> n+1, d.h. f(n+2)--> f((n+1)+2)
> f((n+1)+2)=f(n+3)=n+3 ist zu zeigen
>
> f(n+3)=2*f((n+1)+1)-f(n+1)=2*f(n+2)-f(n+1)= jetzt wirds
> spannend, darf ich für f(n+2)=n+2
das ja!
> und f+r f(n+1)=n+1
> voraussetzen
Das ist hier ein Problem, wenn Du nicht auch auf [mm] $f(2)=2\,$ [/mm] am Anfang hinweist.
Denn ohne [mm] $f(2)=2\,$ [/mm] geht hier alles schief!
Aber lies Dir mal meine Antwort durch. Ebris Antwort ist auch nicht wirklich
falsch, jedenfalls vermutlich nicht aus seiner/ihrer Sicht, weil er/sie das,
was ich dort kritisiere, vermutlich einfach in Gedanken gemacht hat. Wenn
man es nicht erwähnt, wird es aber übersehen, und eventuell wird er/sie
das auch übersehen, wenn er/sie nach ein paar Monaten nochmal die
Aufgabe so lösen will.
Das kritische dabei ist:
Wenn ich nur $f(2) [mm] \not=2$ [/mm] habe, etwa [mm] $f(2):=4\,,$ [/mm] so wirst Du das im Beweis
"übersehen" (denn der Induktionsstart startet mit [mm] $f(3)=3\,,$ [/mm] und im Induktionsschritt
wird aber auch [mm] $f(n+1)\,$ [/mm] verwendet, was für [mm] $n=1\,$ [/mm] gerade [mm] $f(2)\,$ [/mm] ist.)
M.a.W.: Da "fehlt" etwas bzw. zumindest wird ein wichtiges Wissen nicht
genügend "gewürdigt".
P.P.S. Damit es deutlicher wird:
Nimm mal [mm] $f(1):=5\,$ [/mm] und [mm] $f(2):=4\,.$ [/mm] Und jetzt behaupte auch mal
[mm] $f(n+2)=n+2\,$ [/mm] für alle natürlichen $n [mm] \ge 1\,.$
[/mm]
Für [mm] $n=1\,$ [/mm] gilt
[mm] $f(n+2)=f(3)=2*f(2)-f(1)=2*4-5=3\,.$
[/mm]
Passt also.
$n [mm] \to [/mm] n+1$:
$f(n+3)=2*f(n+2)-f(n+1)=...$
So, das sieht vielleicht alles wie bei Dir aus. Und trotzdem ist schon
$f(4)=2*f(3)-f(2)=2*3-4=6-4=2 [mm] \not=4\,.$
[/mm]
Erkennst Du den "Haken"?
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 04:22 Fr 22.11.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Korrektur) kleiner Fehler  | | Datum: | 00:57 Fr 22.11.2013 | | Autor: | Marcel |
Hallo,
> > Hallo zusammen,
> >
> > ich sitze seit 2 Tagen an einer Aufgabe. Und zwar geht es
> > um folgendes:
> >
> > Sei f: N-->N rekursiv definiert durch f(n+2)=2f(n+1)-f(n).
> > Finde geschlossene Ausdrücke (explizite) für fn, falls
> > a) f1=1, f2=2
> > b) f1=1, f2=3
> >
> > Beweise Gültigkeit mittels vollständiger Induktion.
> > Also die expliziten Ausdrücke habe ich für a) und b)
> > gefunden.
> >
> > a) f(n)=n und b) f(n)=2n-1
> >
> > Nun zu meinem Problem, diese ausdrücke per vollständiger
> > Induktion zu beweisen. Ich habe mit a) angefangen, hänge
> > jedoch. Ich notiere alles, was ich habe:
> >
> > Induktionsbehauptung: f(n)=n
> > Induktionsanfang: n=1, das hieße f(1)=1, das stimmt
> mit
>
> Nein.
> Für den Induktionsanfang n=1 muss man hier Zeigen
> f(1+2)=f(3)=3
>
> > der Vorgabe überein, da ja bereits in der Aufgabe f1=1
> > gegeben wird.
> > Induktionsvoraussetzung: für n sei dies wahr und kann
> > weiter genutzt werden.
> >
> > Induktionsschritt: n --> n+1, d.h. f(n+1)=n+1 ist zu
> > zeigen
>
> Auch nicht richtig.
> n -> n+1 d.h. f(n+2) -> f((n+1)+2)
>
> Also ist zur zeigen: f((n+1)+2) = f(n+3) = n+3
>
> f((n+1)+2) = 2f((n+1)+1)-f(n+1) ... hier kommt die
> Induktionsvoraussetzung ins Spiel
das stimmt so leider nicht ganz, es ist unvollständig. Mit Deiner Vorgehensweise
würdest Du begründen (wollen), dass mit [mm] $f(3)=3\,$ [/mm] und
[mm] $f(n+2)=2f(n+1)-f(n)\,$
[/mm]
folgen würde, dass $f(n+2)=n+2$ für alle $n=1,2,3,...$ gilt. Das wäre "nur"
der Beweis von [mm] $f(m)=m\,$ [/mm] für alle $m=3,4,5,...$
Wenn Du sagst, dass Du mit [mm] $f(3)=3\,$ [/mm] startest, dann mache mal "von Hand"
den Induktionsschritt
aus [mm] $f(3)=3\,$ [/mm] folgt [mm] $f(4)=4\,:$
[/mm]
Der sieht dann so aus
[mm] $f(4)=f(2+2)=2*f(2+1)-f(2)=2*f(3)-f(2)=2*3-\red{\,f(2)\,}=6-\red{\,f(2)}\,.$
[/mm]
In Deinem Induktionsbeweis nimmst Du aber nirgendwo das Wissen [mm] $f(2)=2\,$
[/mm]
mit. Ohne das geht aber der ganze Beweis schief!
P.S. Du kannst das natürlich korrigieren, indem Du zuerst
[mm] $f(3)=3\,$ [/mm] und [mm] $f(4)=4\,$
[/mm]
im Induktionsstart nachrechnest (im Induktionsschritt soll dann $n [mm] \ge [/mm] 2$ sein).
Oder aber Du erwähnst halt, dass [mm] $f(2)=2\,$ [/mm] war. Du brauchst im
Induktionsstart hier jedenfalls zwei(!) "Nachweise". (Im Induktionsschritt
musst Du ja quasi auch auf zwei vorangegangene Werte zugreifen!)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Korrektur) richtig (detailiert geprüft)  | | Datum: | 01:41 Fr 22.11.2013 | | Autor: | Ebri |
Wenn ich alles richtig verstanden habe ist zu zeigen:
f(n) = n , wenn f(1)=1, f(2)=2 und f(n+2)=2f(n+1)-f(n)
Also nehmen wir mal an f(1)=1 und f(2)=2. => Für [mm] n\le2 [/mm] ist f(n)=n erfüllt.
Fehlen noch n>2.
f(n+2)=2f(n+1)-f(n) kann man auch schreiben als f(n)=2f(n-1)-f(n-2).
Zz: f(n)=2f(n-1)-f(n-2)=n für n>2.
IA: n = 3
f(3)=2f(2)-f(1)=2*2-1=3
IV:
f(n)=2f(n-1)-f(n-2)=n für n>2
IS: n -> n+1
f(n+1)=2f(n)- f(n-1)=2n- f(n-1)=2n-(n-1)= n+1
Die Frage ist jetzt ob f(n-1) schon nachgewiesen wurde. Ich meine schon, da wir alle Fälle [mm] n\le3 [/mm] bereits abgedeckt haben.
Man sollte das Beweis noch explizit erwähnen, da hast du recht.
Gruß
Ebri
|
|
|
| |
|
| Status: |
(Korrektur) oberflächlich richtig  | | Datum: | 01:55 Fr 22.11.2013 | | Autor: | Marcel |
Hallo Ebri,
> Wenn ich alles richtig verstanden habe ist zu zeigen:
> f(n) = n , wenn f(1)=1, f(2)=2 und f(n+2)=2f(n+1)-f(n)
>
> Also nehmen wir mal an f(1)=1 und f(2)=2. => Für [mm]n\le2[/mm] ist
> f(n)=n erfüllt.
das ist ein wichtiger Punkt, der nicht unterschlagen werden kann/darf!
> Fehlen noch n>2.
>
> f(n+2)=2f(n+1)-f(n) kann man auch schreiben als
> f(n)=2f(n-1)-f(n-2).
>
> Zz: f(n)=2f(n-1)-f(n-2)=n für n>2.
>
> IA: n = 3
> f(3)=2f(2)-f(1)=2*2-1=3
>
> IV:
> f(n)=2f(n-1)-f(n-2)=n für n>2
>
> IS: n -> n+1
> f(n+1)=2f(n)- f(n-1)=2n- f(n-1)=2n-(n-1)= n+1
>
>
> Die Frage ist jetzt ob f(n-1) schon nachgewiesen wurde. Ich
> meine schon, da wir alle Fälle [mm]n\le3[/mm] bereits abgedeckt
> haben.
>
> Man sollte das Beweis noch explizit erwähnen, da hast du
> recht.
Wie gesagt: Ich kann auch [mm] $f(1):=5\,$ [/mm] und [mm] $f(2):=4\,$ [/mm] setzen. Du hattest gesagt:
Weise [mm] $f(3)=3\,$ [/mm] nach und führe für $n [mm] \in \IN$ [/mm] den Induktionsschritt $n [mm] \to [/mm] n+1$ aus:
[mm] $f(n+3)=2*f(n+2)-f(n+1)\,.$
[/mm]
Für [mm] $n=1\,$ [/mm] steht dann da
[mm] $f(4)=2*f(3)-f(2)=2*3-f(2)=6-f(2)\,.$
[/mm]
In Deinem Induktionsbeweis erwähnst Du [mm] $f(2)=2\,,$ [/mm] so, wie es ursprünglich
in der Aufgabe stand, gar nicht mehr. Und ich habe hier extra mal [mm] $f(2)\,$ [/mm] anders
definiert, so dass trotzdem [mm] $f(3)=3\,$ [/mm] ist.
D.h., wenn Du so, wie Du es gemacht hast, im Induktionsbeweis nicht [mm] $f(2)=2\,$
[/mm]
"mitnimmst", naja, dann geht der Induktionsschritt von [mm] $n=1\,$ [/mm] nach [mm] $\tilde{n}:=n+1=2$
[/mm]
schon schief. Denn um [mm] $f(4)\,$ [/mm] zu berechnen, muss man wissen, was mit [mm] $f(2)\,$ [/mm] "los war".
So, wie Du es jetzt aufgeschrieben hast, würde das niemand mehr
kritisieren. Aber viele würden auch einfach die Wichtigkeit von [mm] $f(2)=2\,$ [/mm] in Deinem
Induktionsbeweis nicht mehr wahrnehmen.
Gruß,
Marcel
|
|
|
|
