Vollständige Induktion..diesmal mit einer rekursiven Zahlenfolge :-(

29.10.2007, 15:37

matheinteressent

Vollständige Induktion..diesmal mit einer rekursiven Zahlenfolge :-(

Hallo, bräuchte mal dringend Hilfe bei der folgenden Aufgabe. Es soll meine erste Hausaufgabe an der Uni sein, wills natürlich nicht verhauen. Leider bin ich es nicht gewohnt rekursive Zahlenfolge durch vollst. Induktion zu beweisen. Mein Prof konnte es auch nicht so richtig erklären..Im netzt habe ich auch keine Aufgabe gleichen Typs gefunden..

Sei $\begin{eqnarray*} u_1=1, u_2=2 \end{eqnarray*}$ und $\begin{eqnarray*} u_n=u_{n-1}+u_{n-2} \end{eqnarray*}$ für $\begin{eqnarray*} n =3,4,5 ... \end{eqnarray*}$

Zeigen Sie, dass dadurch eine rekursive Zahlenfolge $\begin{eqnarray*} (u_n) \end{eqnarray*}$ für $\begin{eqnarray*} n=1,2,3... \end{eqnarray*}$ definiert ist, so dass $\begin{eqnarray*} u_n \leq (\frac{7}{4})^n \end{eqnarray*}$ , $\begin{eqnarray*} \forall n \in \mathbb N \end{eqnarray*}$

Bin bis zu der folgenden Stelle gekommen:

1. $\begin{eqnarray*} A_0 (3) \end{eqnarray*}$ ist wahr
2. Dann nehme ich an $\begin{eqnarray*} A(n) \end{eqnarray*}$ ist wahr, daraus folgt, dass auch $\begin{eqnarray*} A(n+1) \end{eqnarray*}$ wahr ist
3. Somit gilt
$\begin{eqnarray*} u_{n+1}=u_{(n+1)-1}+u_{(n+1)-2} \leq (\frac{7}{4})^n+(\frac{7}{4})^{n-1} \end{eqnarray*}$

$\begin{eqnarray*} u_{n+1}=u_{n}+u_{(n-1)} \leq (\frac{7}{4})^n+(\frac{7}{4})^{n-1} \end{eqnarray*}$

...???

So und nun habe ich ein Verständnisproblem, weiß leider nicht was ich als nächstes tun soll und weiß auch nicht so recht, was als Schlussfolgerung stehen soll..Vielleicht ist mein Anstatz auch nicht richtig gewählt..Hoffe einer von euch hatte die Aufgabe schon mal selbst, würde mich über jede Mithilfe freuen! Danke an alle im voraus! Gruß :-)

29.10.2007, 16:01

klarsoweit

Auf diesen Beitrag antworten »

RE: Vollständige Induktion..diesmal mit einer rekursiven Zahlenfolge :-(
Das Ziel deiner vollständigen Induktion ist doch, daß du zeigst, daß auch A(n+1) wahr ist, wenn A(n) wahr ist.
Dazu wäre es ganz gut, wenn du die Aussage A(n+1) mal komplett hinschreibst, damit man mal sieht, wo denn das Ziel ist.

Zu deiner Rechnung noch ein Tipp:
Klammere in der letzten Zeile $\begin{eqnarray*} \left( \frac 7 4 \right)^{n-1} \end{eqnarray*}$ aus.

29.10.2007, 16:08

matheinteressent

Auf diesen Beitrag antworten »

RE: Vollständige Induktion..diesmal mit einer rekursiven Zahlenfolge :-(
hey..!
genau dann kommt auf der einen Seite folgendes raus:

... = $\begin{eqnarray*} (\frac{7}{4}+1)(\frac{7}{4})^{n-1} \end{eqnarray*}$

So nun weiß ich nicht weiter..Komm einfach nicht auf die Idee, wie ich den Schluss gestalten soll. Gruß

29.10.2007, 17:51

klarsoweit

Auf diesen Beitrag antworten »

RE: Vollständige Induktion..diesmal mit einer rekursiven Zahlenfolge :-(
unglücklich

Deswegen hatte ich ja gesagt, daß du mal hinschreibst, wo du überhaupt hin willst. Wie will man eine Aufgabe rechnen, wenn man noch nicht mal weiß, was das Ziel ist.

Also, schätze 11/4 nach oben ab durch 49/16.

29.10.2007, 21:49

matheinteressent

Auf diesen Beitrag antworten »

RE: Vollständige Induktion..diesmal mit einer rekursiven Zahlenfolge :-(
Ok du hast recht...also dann versuch ich's einfach mal. Mein Ziel ist zu beweisen, dass $\begin{eqnarray*} \forall n \in \mathbb N \end{eqnarray*}$ die Gleichung $\begin{eqnarray*} u_n \leq (\frac{7}{4})^n \end{eqnarray*}$ . A(n) ist wahr, somit ist A(n+1) wahr (zumindest ist das die Annahme...). Also sei A(n+1) gegeben durch

$\begin{eqnarray*} u_{n+1}=u_n+u_{n-1} \leq (\frac{7}{4})^n+(\frac{7}{4})^{n-1} \end{eqnarray*}$

und soll wahr sein. Ich setze $\begin{eqnarray*} (\frac{7}{4})^n \end{eqnarray*}$ in $\begin{eqnarray*} u_{n+1} \end{eqnarray*}$ , womit die nächstfolgende Zahl ausgedrückt wird.

Ich löse also die Ungleichung, d.h. ich klammere sie aus (wie du schon gesagt hast) bis ich einen Ausdruck mit (n+1) erhalte:

$\begin{eqnarray*} u_{n+1}=u_n+u_{n-1} \leq ((\frac{7}{4})+1)(\frac{7}{4})^{n-1} \end{eqnarray*}$

$\begin{eqnarray*} \leq (\frac{11}{4})(\frac{7}{4})^{n-1} \end{eqnarray*}$

$\begin{eqnarray*} \leq (\frac{11}{4})\frac{(\frac{7}{4})^n}{\frac{7}{4}} \end{eqnarray*}$

$\begin{eqnarray*} (\frac{49}{16}) (u_{n+1}) \leq (\frac{11}{4})(\frac{7}{4})^{n+1} \end{eqnarray*}$ // dividiert durch 49/16

$\begin{eqnarray*} u_{n+1}=u_n+u_{n-1} \leq (\frac{44}{49})(\frac{7}{4})^{n+1} \end{eqnarray*}$

Hoffe meine Rechnung geht in die richtige Richtung. Ich würde sagen, A(n) ist wahr, da durch Probe bei beliebigen n immer die Ungleichung stimmt...Ich freue ich mich über jeden Korrekturvorschlag! Danke vielmals! Gruß matheinteressent

30.10.2007, 10:08

klarsoweit

Auf diesen Beitrag antworten »

RE: Vollständige Induktion..diesmal mit einer rekursiven Zahlenfolge :-(
O wei, o wei. traurig

Zitat:

Original von matheinteressent
Ok du hast recht...also dann versuch ich's einfach mal. Mein Ziel ist zu beweisen, dass $\begin{eqnarray*} \forall n \in \mathbb N \end{eqnarray*}$ die Gleichung $\begin{eqnarray*} u_n \leq (\frac{7}{4})^n \end{eqnarray*}$ . A(n) ist wahr, somit ist A(n+1) wahr (zumindest ist das die Annahme...).

Die unpräzisen Formulierungen lassen offenkundig werden, daß du das formale Prinzip der vollständigen Induktion nicht beherrscht.

Erstmal ist eine Ungleichung zu zeigen, nämlich:
$\begin{eqnarray*} A(n): u_n \leq (\frac{7}{4})^n \end{eqnarray*}$ für alle n aus N.

Beim Induktionsschritt nimmst du an, daß diese Ungleichung für beliebiges, aber festes n wahr ist. Unter dieser Annahme mußt du zeigen, daß dann auch A(n+1) wahr ist.

Zitat:

Original von matheinteressent
Also sei A(n+1) gegeben durch

$\begin{eqnarray*} u_{n+1}=u_n+u_{n-1} \leq (\frac{7}{4})^n+(\frac{7}{4})^{n-1} \end{eqnarray*}$

und soll wahr sein.

Das ist nicht A(n+1). Deswegen habe ich auch darauf gedrängt, daß du das mal hinschreibst. Richtig wäre:

$\begin{eqnarray*} A(n+1): u_{n+1} \leq (\frac{7}{4})^{n+1} \end{eqnarray*}$

Man braucht in A(n) nur alle n durch n+1 ersetzen. Richtig ist dann, daß du mit der linken Seite anfängst:
$\begin{eqnarray*} u_{n+1}=u_n+u_{n-1} \end{eqnarray*}$

Zitat:

Original von matheinteressent
Ich setze $\begin{eqnarray*} (\frac{7}{4})^n \end{eqnarray*}$ in $\begin{eqnarray*} u_{n+1} \end{eqnarray*}$ , womit die nächstfolgende Zahl ausgedrückt wird.

Hää?

Wo willst du das gemacht haben? Abgesehen davon, daß $\begin{eqnarray*} u_{n+1} \end{eqnarray*}$ nicht $\begin{eqnarray*} (\frac{7}{4})^n \end{eqnarray*}$ ist. Allenfalls kannst du u_n nach oben durch $\begin{eqnarray*} (\frac{7}{4})^n \end{eqnarray*}$ und u_{n-1} nach oben durch $\begin{eqnarray*} (\frac{7}{4})^{n-1} \end{eqnarray*}$ mit Hilfe der Induktionsannahme A(n) abschätzen. Das hast du ja auch im Prinzip gemacht.

Kleiner Hinweis: hier wird nicht nur A(n), sondern auch A(n-1) benötigt. Du mußt also auch voraussetzen, daß neben A(n) auch A(n-1) wahr ist. Entsprechend muß man beim Induktionsanfang die Gültigkeit von A(1) und A(2) zeigen.

So, nun haben wir:

$\begin{eqnarray*} u_{n+1}=u_n+u_{n-1} \leq (\frac{7}{4})^n+(\frac{7}{4})^{n-1} = (\frac 7 4 + 1) \cdot (\frac{7}{4})^{n-1} \end{eqnarray*}$

Zitat:

Original von matheinteressent
$\begin{eqnarray*} \leq (\frac{11}{4})(\frac{7}{4})^{n-1} \end{eqnarray*}$

$\begin{eqnarray*} \leq (\frac{11}{4})\frac{(\frac{7}{4})^n}{\frac{7}{4}} \end{eqnarray*}$

$\begin{eqnarray*} (\frac{49}{16}) (u_{n+1}) \leq (\frac{11}{4})(\frac{7}{4})^{n+1} \end{eqnarray*}$ // dividiert durch 49/16

$\begin{eqnarray*} u_{n+1}=u_n+u_{n-1} \leq (\frac{44}{49})(\frac{7}{4})^{n+1} \end{eqnarray*}$

Hoffe meine Rechnung geht in die richtige Richtung. Ich würde sagen, A(n) ist wahr, da durch Probe bei beliebigen n immer die Ungleichung stimmt...Ich freue ich mich über jeden Korrekturvorschlag! Danke vielmals! Gruß matheinteressent

Also komplizierter ging deine Rechnung nicht. Vor allem der letzte Satz ist unglaublich. Also eine allgemeine Aussage gilt deswegen, weil du durch eine Handvoll Proben rausbekommst, daß diese da stimmt. Desweiteren wollen wir im Induktionsschritt nicht A(n) zeigen (die Gültigkeit wird im Gegenteil sogar vorausgesetzt), sondern A(n+1). Und wenn du meinen Tipp mit der Abschätzung von 11/4 durch 49/16 richtig befolgt hättest, würde das so gehen:

$\begin{eqnarray*} u_{n+1}=u_n+u_{n-1} \leq (\frac{7}{4})^n+(\frac{7}{4})^{n-1} = (\frac 7 4 + 1) \cdot (\frac{7}{4})^{n-1} \end{eqnarray*}$

$\begin{eqnarray*} \leq \frac{49}{16} \cdot (\frac{7}{4})^{n-1} = (\frac{7}{4})^{n+1} \end{eqnarray*}$

Also ist $\begin{eqnarray*} u_{n+1} \leq (\frac{7}{4})^{n+1} \end{eqnarray*}$ und damit A(n+1) wahr.

30.10.2007, 10:42

matheinteressent

Auf diesen Beitrag antworten »

hey..danke erstmal..ich gibs zu, das mathematische denken ist nicht so mein ding..ich arbeite dran! aber mühe habe ich mir gegeben..leider gibts es auch fast gar keine übungsbücher, wo man umfangreich so was üben kann unglücklich

Zitat:

Kleiner Hinweis: hier wird nicht nur A(n), sondern auch A(n-1) benötigt. Du mußt also auch voraussetzen, daß neben A(n) auch A(n-1) wahr ist. Entsprechend muß man beim Induktionsanfang die Gültigkeit von A(1) und A(2) zeigen.

das verstehe ich nicht. warum muss ich denn A(n-1) beweisen, wenn die in jedem Lehrbuch immer was von A(n+1) steht..?

Zitat:

irgendwie weiß ich immernoch nicht was du mit "11/4 nach oben ab durch 49/16" meinst..vor allem warum verschwindet dann 11/4 auf einmal?

ich danke dir wirklich herzlich, hast mir auf jedenfall schon ne menge geholfen! gruß

30.10.2007, 11:01

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von matheinteressent
das verstehe ich nicht. warum muss ich denn A(n-1) beweisen, wenn die in jedem Lehrbuch immer was von A(n+1) steht..?

Es wird ja auch nicht A(n-1) bewiesen, sondern dessen Gültigkeit wird wegen der Verwendung von $\begin{eqnarray*} u_{n-1} \leq (\frac{7}{4})^{n-1} \end{eqnarray*}$ benötigt bzw. vorausgesetzt. Im Prinzip lautet der Induktionsschritt diesmal nicht
$\begin{eqnarray*} A(n) \Rightarrow A(n+1) \end{eqnarray*}$
sondern
$\begin{eqnarray*} A(n-1) \text{ und } A(n) \Rightarrow A(n+1) \end{eqnarray*}$

Deswegen braucht man beim Induktionsanfang A(1) und A(2), um dann beim ersten Induktionsschritt für n=2 die Gültigkeit für A(3) zu bekommen.

Zitat:

Original von matheinteressent
irgendwie weiß ich immernoch nicht was du mit "11/4 nach oben ab durch 49/16" meinst..vor allem warum verschwindet dann 11/4 auf einmal?

Ich ersetze 11/4 durch 49/16. Wegen $\begin{eqnarray*} \frac 7 4 + 1 = \frac{11}{4} < \frac{49}{16} \end{eqnarray*}$ wird die rechte Seite der Ungleichung nur noch größer.

31.10.2007, 11:49

matheinteressent

Auf diesen Beitrag antworten »

Hey..! Ich habe nochmal mich damit beschäftigt, habe mich mal mit deinen Aussagen beschäftigt und dazu auch ein paar Bücher zur Hand genommen.

Zitat:

Prinzip lautet der Induktionsschritt diesmal nicht
$\begin{eqnarray*} A(n) \Rightarrow A(n+1) \end{eqnarray*}$
sondern
$\begin{eqnarray*} A(n-1) \text{ und } A(n) \Rightarrow A(n+1) \end{eqnarray*}$

Dieses ist mir auf jedenfall klar geworden und ist auch ziemlich logisch..! Hammer

danke!

Zitat:

Ich ersetze 11/4 durch 49/16. Wegen $\begin{eqnarray*} \frac 7 4 + 1 = \frac{11}{4} < \frac{49}{16} \end{eqnarray*}$ wird die rechte Seite der Ungleichung nur noch größer.

das verstehe ich aber immernoch nicht, was du damit meinst..
warum verschwindet hier auf einmal 11/4? vielleicht erklärst du das kurz, warum das 11/4 in der ungleichung einfach so verschwindet - der term war doch zu kurz von dir, als das ich das einfach so einsehen könnte..! Ich glaub die Schwierigkeit hier liegt in der Ungleichung.. Danke wiedermal Gott

Gruß

31.10.2007, 12:07

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von matheinteressent
das verstehe ich aber immernoch nicht, was du damit meinst..
warum verschwindet hier auf einmal 11/4? vielleicht erklärst du das kurz, warum das 11/4 in der ungleichung einfach so verschwindet - der term war doch zu kurz von dir, als das ich das einfach so einsehen könnte..!

Also eigentlich dürfte ich diese Frage im Hochschulbereich gar nicht beantworten. Also mal ehrlich: wer bei einer solchen Frage rückwärts umfällt, wird auf der Hochschule nicht weit kommen. Sorry, das mußte mal gesagt werden.

Also nochmal für die gaaanz langsam Denkenden:

Wir haben den Term $\begin{eqnarray*} A := (\frac 7 4 + 1) \cdot (\frac{7}{4})^{n-1} \end{eqnarray*}$ .

Nun haben wir in der 5. Klasse gelernt, daß $\begin{eqnarray*} (\frac 7 4 + 1) = \frac{11}{4} = \frac{44}{16} \leq \frac{49}{16} \end{eqnarray*}$ ist.

Wenn ich also im Term A den Faktor $\begin{eqnarray*} (\frac 7 4 + 1) \end{eqnarray*}$ durch $\begin{eqnarray*} \frac{49}{16} \end{eqnarray*}$ ersetze, dann wird aus dem Term A ein neuer Term, der im Vergleich zu A größer ist. Also:

$\begin{eqnarray*} (\frac 7 4 + 1) \cdot (\frac{7}{4})^{n-1} \leq \frac{49}{16} \cdot (\frac{7}{4})^{n-1} \end{eqnarray*}$

Also ausführlicher geht es wirklich nicht.

31.10.2007, 12:52

matheinteressent

Auf diesen Beitrag antworten »

klick! vielen dank.. Freude

also die note geht auf dein konto!

Zitat:

Ich schiebe nicht gern die Schuld auf andere, aber ich hatte seit der 5. Klasse jedes Jahr einen anderen Lehrer bis zum Abitur. Und nur vielleicht 1 von denen war kompetent genug und auch kompetent genug auf meine Fragen zu antworten. Erst im Abitur habe gemerkt, was ich alles nicht gelernt habe. Ich habe großes mathematisches Interesse aber ich habe nicht das Handwerkszeug bekommen. Aber ich finde es richtig das alles nachzuholen und deshalb stelle ich auch Fragen. (Ich meine nur weil ich diese eine Frage gestellt habe, heißt es ja nicht, dass ich überall in Mathe nicht durchsehe..) Naja..ciao :-)

Neue Frage »

Antworten »

Vollständige Induktion..diesmal mit einer rekursiven Zahlenfolge :-(

Verwandte Themen