Vollständige Induktion mit Zahlenfolgen

11.05.2018, 22:32

Buffon is N°1

Vollständige Induktion mit Zahlenfolgen

Meine Frage:
Hallo!

Ich sitze grade hier an einer Aufgabe in der Informatik, wo mithilfe vollständiger Induktion belegen soll, ob ungleichungen zutreffen oder nicht.

Die Aufgabe an sich ist aber zweitrangig für dieses Thread. Ich finde einfach keine Erklärung/Beispiel, wie ich Zahlenreihen mit Vollständiger Induktion kombinieren kann.
(In Mathe bin ich auch nicht sonderlich begabt, aber so lange ich halbwegs ordentlich formulierte Erklärungen bekomme, klappt das, wie z.B. mit diesem Video: https://www.youtube.com/watch?v=G1Gb5Laaanc)

Ich kann euch ja mal die Zahlenreihen posten:

$\begin{eqnarray*} n \geq 2 a_{0} = 1 a_{1} = 1 a_{n} = 3 * a_{n-2} + a_{n-1} \end{eqnarray*}$

EDIT(Helferlein): Latex repariert.
Früher oder Später muss ichs ja eh können, dementsprechend wär mir eine Demonstration/ein bereits vorhandenes Tutorial lieber als eine Lösung

Meine Ideen:
Bis zum Induktionsschritt geht eigentlich alles Big Laugh

11.05.2018, 23:58

sibelius84

Auf diesen Beitrag antworten »

Hi,

da du eine rekursive Folge angegeben hast, rate ich mal, dass es dir darum geht, diese in eine explizite Form zu überführen. Richtig? Also wenn du z.B. gegeben hättest: $\begin{eqnarray*} a_0:=1, a_{n+1}:=2a_n ,\, n\geq 0 \end{eqnarray*}$ , dann wäre die explizite Angabe $\begin{eqnarray*} a_n=2^n \end{eqnarray*}$ die von dir gewünschte Lösung?

Da könnte man einerseits natürlich durch 'Erraten' hinkommen. In meinem obigen Beispiel ist das einfach. Bei deinem weiß ich es nicht. (1,1,4,7,19,40,97,217,...), also ich vermag da nicht wirklich ein Schema zu erkennen. Obwohl, ein Versuch: Die 'interessanten' Abstände hinten sind 12, 21, 57, 120. Das entspricht gerade 3·4,3·7,3·19,3·40. Ich sehe aber auch nicht, wie das weiterbringt. Mündet letztlich nur wieder in der Rekursionsvorschrift.

Also überlegt man sich was anderes:
In meinem einfachen Beispiel oben hatten wir gesehen, dass eine Potenzfolge der Form c^n (hier mit c=2) das Problem löst. Also versuchen wir einfach mal den Ansatz $\begin{eqnarray*} a_n:=c^n \end{eqnarray*}$ in die Rekursionsvorschrift einzusetzen:

$\begin{eqnarray*} c^n=3c^{n-2}+c^{n-1}\qquad\qquad\vert :c^{n-2};\, -c-3 \end{eqnarray*}$

$\begin{eqnarray*} \Leftrightarrow c^2-c-3=0 \end{eqnarray*}$

Die pq-Formel liefert dir zwei Lösungen c1, c2, so dass also die Folgen $\begin{eqnarray*} x_n:=c_1^n \end{eqnarray*}$ und $\begin{eqnarray*} y_n:=c_2^n \end{eqnarray*}$ die angegebene Rekursion erfüllen. Mit den beiden Folgen gilt dies auch für jede beliebige Linearkombination $\begin{eqnarray*} Ax_n+By_n,\; A,B\in\mathbb R \end{eqnarray*}$ . Wenn du hier noch deine Startwerte a0, a1 einsetzt, erhältst du ein LGS, aus dem du A, B und damit insgesamt die explizite Formel der Folge bestimmen kannst.

LG
sibelius84

13.05.2018, 01:26

vvfvvfvvf

Auf diesen Beitrag antworten »

TS hier (ich hab meinen alten Account wiedergefunden):

Ich versteht nur Bahnhof. Kannst du mir vielleicht kurz zusammenfassen/ Tipps geben was man machen muss/sollte bei Induktion mit Zahlenfolgen?

13.05.2018, 06:38

HAL 9000

Auf diesen Beitrag antworten »

Vielleicht sollten wir zuerst klären, was du überhaupt mit dieser Zahlenfolge anzustellen gedenkst. Das hier

Zitat:

Original von Buffon is N°1
Ich finde einfach keine Erklärung/Beispiel, wie ich Zahlenreihen mit Vollständiger Induktion kombinieren kann.
[...]
was man machen muss/sollte bei Induktion mit Zahlenfolgen

ist jedenfalls völlig nebulös: Vollständige Induktion ist kein Selbstzweck, sondern ein Beweisverfahren. Es bedarf also irgendeiner Behauptung über deine Zahlenfolgen, die du beweisen willst!

sibelius84 vermutet, dass du eine explizite Darstellung deiner rekursiv gegebenen Folge finden bzw. dann auch beweisen willst. Das hier

Zitat:

Original von Buffon is N°1
wo mithilfe vollständiger Induktion belegen soll, ob ungleichungen zutreffen oder nicht.

deutet aber eher drauf hin, dass irgendeine Ungleichung in Bezug auf diese Zahlenfolge zu beweisen ist, z.B. $\begin{eqnarray*} 2^n < a_n < 3^n \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq 4 \end{eqnarray*}$ , o.ä. verwirrt

Also nenne doch bitte mal diese nachzuweisende Ungleichung, damit dieses Ratespiel hier beendet ist!

13.05.2018, 11:11

sibelius84

Auf diesen Beitrag antworten »

Ok, das mit den "Ungleichungen beweisen" hatte ich überlesen. Da kann ich mich der Aufforderung von HAL 9000, die Aufgabenstellung zu konkretisieren, nur anschließen!

Zitat:

Original von vvfvvfvvf
Ich versteht nur Bahnhof. Kannst du mir vielleicht kurz zusammenfassen/ Tipps geben was man machen muss/sollte bei Induktion mit Zahlenfolgen?

Dann würde ich meinen obigen Beitrag noch mal posten und du würdest wieder nur Bahnhof verstehen - ein Teufel

skreis! Daher wäre es doch wesentlich sinnvoller, wenn du konkret sagst, welche Teile meines Posts du verstanden hast und welche nicht. Ich denke etwa, das Beispiel, das ich in den ersten zwei Zeilen genannt habe, sollte ohne Weiteres nachvollziehbar sein, wenn man mit den Standard-Notationen bei Folgen vertraut ist. Schreib es dir mal sauber auf, ich denke, dann wird es schon sehr bald 'klick' machen.

15.05.2018, 23:08

vvfvvfvvf

Auf diesen Beitrag antworten »

Eine der beiden ungleichungen ist:

$\begin{eqnarray*} a_{n} \leq 3^{n} \end{eqnarray*}$
Ein durchgerechnetes Beispiel wär hilfreich, der Prof hat dazu kein Beispiel in seinen Folien und jetzt hock ich hier Big Laugh

16.05.2018, 07:18

HAL 9000

Auf diesen Beitrag antworten »

Der Beweis der Induktionsbehauptung $\begin{eqnarray*} a_{n+1}\leq 3^{n+1} \end{eqnarray*}$ wird wesentlich auf der Rekursionsgleichung $\begin{eqnarray*} a_{n+1} = 3a_{n-1} + a_n \end{eqnarray*}$ beruhen. Da dazu im weiteren im Induktionsschritt auf die Induktionsvoraussetzung nicht nur in der Form $\begin{eqnarray*} a_n\leq 3^n \end{eqnarray*}$ sondern auch $\begin{eqnarray*} a_{n-1}\leq 3^{n-1} \end{eqnarray*}$ zurückgegriffen werden muss, ist das nicht nur eine Volständige Induktion in der "reinen" Form $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ , sondern eher $\begin{eqnarray*} n-1,n\to n+1 \end{eqnarray*}$ bzw. allgemeiner $\begin{eqnarray*} (\leq n)\to n+1 \end{eqnarray*}$ .

Das bedeutet insbesondere, dass der Induktionsanfang für die ersten zwei $\begin{eqnarray*} n \end{eqnarray*}$ -Werte durchzuführen ist, sonst funktioniert die Schlussweise nicht.

D.h. folgende Vorgehensweise wäre die naheliegende:

Im Induktionsanfang beweist du die Behauptung für $\begin{eqnarray*} n=0 \end{eqnarray*}$ und (!) $\begin{eqnarray*} n=1 \end{eqnarray*}$ ,

Im Induktionsschritt $\begin{eqnarray*} (\leq n)\to n+1 \end{eqnarray*}$ ist $\begin{eqnarray*} a_{n+1} = 3a_{n-1} + a_n\leq \ldots \leq 3^{n+1} \end{eqnarray*}$ nachzuweisen, unter Benutzung von $\begin{eqnarray*} a_n\leq 3^n \end{eqnarray*}$ und $\begin{eqnarray*} a_{n-1}\leq 3^{n-1} \end{eqnarray*}$ .

Neue Frage »

Antworten »

Vollständige Induktion mit Zahlenfolgen

Verwandte Themen