Vollständige Induktion mit 2 Vorgängern

07.01.2010, 16:35

tardezyx

Vollständige Induktion mit 2 Vorgängern

Hallo Leute,

es geht um folgende Aufgabe:

Zitat:

Beweisen Sie mittels vollständiger Induktion, dass man die rekursiv gegebenen Werte

$\begin{eqnarray*} a_{n} \end{eqnarray*}$

$\begin{eqnarray*} a_{0} = a_{1} = 1 \end{eqnarray*}$

$\begin{eqnarray*} a_{n} = 6 * a_{n-2} - a_{n-1} , n \geq 2 \end{eqnarray*}$

durch die explizite Formel

$\begin{eqnarray*} a_{n} = \frac{1}{5} * ( 2^{n+2} + (-3)^{n} ) \end{eqnarray*}$

angeben kann.

Hinweis: Da Sie hier im Induktionsschritt zwei Vorgänger benötigen, müssen Sie den Induktionsanfang auch für zwei aufeinanderfolgende Elemente durchführen.

ich komme bemi Beweis einfach nicht weiter, soweit mein Ansatz:

Induktionsanfang:

$\begin{eqnarray*} n = 2 \Rightarrow a_{2} = (...) = 5 \end{eqnarray*}$
$\begin{eqnarray*} n = 3 \Rightarrow a_{3} = (...) = 1 \end{eqnarray*}$
$\begin{eqnarray*} n = 4 \Rightarrow a_{4} = (...) = 29 \end{eqnarray*}$

Induktionsschritt:

Induktionsvorraussetzung:

$\begin{eqnarray*} n = k \Rightarrow a_{k} = 6 * a_{k-2} - a_{k-1} \Rightarrow a_{k} = \frac{1}{5} * ( 2^{k+2} + (-3)^{k} ) \end{eqnarray*}$

$\begin{eqnarray*} n = k+1 \Rightarrow a_{k+1} = 6 * a_{k-1} - a_{k} \Rightarrow a_{k+1} = \frac{1}{5} * ( 2^{k+3} + (-3)^{k+1} ) \end{eqnarray*}$

Beweis:

$\begin{eqnarray*} 6 * a_{k-1} - a_{k} = 6 * a_{k-2} - a_{k-1} + ??? \end{eqnarray*}$

Was kommt bei dem ??? rein?

Mir ist der fehlende Teil zum Folgeglied vollkommen unklar - also was ich konkret noch summieren muss, um auf den Nachfolger zu kommen. Wie kann ich das denn hier herleiten? Mit einem Folgeglied wie bspw. einer Fakultätenfolge ist das ja noch irgendwie nachzuvollziehen (von k zu k+1: ...+k+1) - aber hier herrscht vollkommenes Unverständis verwirrt

Der Rest des Beweises müsste sich ja dann so ergeben, wie er hiersteht:

$\begin{eqnarray*} \Rightarrow = \frac{1}{5} * ( 2^{k+2} + (-3)^{k} ) + ??? \Rightarrow = \frac{1}{5} * ( 2^{k+3} + (-3)^{k+1} ) \end{eqnarray*}$

Danke jedenfalls schonmal für eure Hilfe!

Gruß!

07.01.2010, 17:28

bernd

Auf diesen Beitrag antworten »

RE: Vollständige Induktion mit 2 Vorgängern
Man muss die Formel für $\begin{eqnarray*} a_{n+1} \end{eqnarray*}$ anstatt $\begin{eqnarray*} a_n \end{eqnarray*}$ nachweisen. Nun ist aber $\begin{eqnarray*} a_{n+1}=6a_{n-1}-a_n \end{eqnarray*}$ . Für die beiden Folgenglieder auf der rechten Seite hat man die explizite Formel aus der Induktionsbehauptung zur Verfügung, die man also einsetzen kann. Danach muss man nur noch etwas umformen.

07.01.2010, 17:32

Auf diesen Beitrag antworten »

Ergänzend sei noch erwähnt, dass der Induktionsanfang für n=0 und n=1 passender gewesen wäre. In der vorliegenden Form fehlt nämlich der Nachweis, dass die nachzuweisende explizite Formel auch für n=0 und n=1 gilt. Augenzwinkern

09.01.2010, 01:05

tardezyx

Auf diesen Beitrag antworten »

Hallo nochmal,

@ Arthur

Wieso sollte ich mit 0 und 1 anfangen? Der Beweis soll doch allgemein sein und die Induktionsbehauptung gilt eh nur für

$\begin{eqnarray*} n\geq 2 \end{eqnarray*}$

@ Bernd

Die Induktionsbehauptung ist doch diese fertige Formel:

$\begin{eqnarray*} a_{n} = \frac{1}{5} * ( 2^{n+2} + (-3)^{n} ) \end{eqnarray*}$

Dann gilt:

$\begin{eqnarray*} a_{n+1}=6a_{n-1}-a_n \end{eqnarray*}$

Und es müsste sich das ergeben:

$\begin{eqnarray*} a_{n+1}=\frac{6 * ( 2^{n+1} + (-3)^{n-1} ) - ( 2^{n+2} + (-3)^{n} )}{5} \end{eqnarray*}$

Ausmultiplizieren ist hier m.W.n. unmöglich.

Muss ich nun also die Induktionsbehauptung so umformen, dass ich auf eben diesen Term komme (wüßte nicht, wie das gehen soll)?

Danke & Gruß!

12.01.2010, 09:46

tardezyx

Auf diesen Beitrag antworten »

Habt ihr noch einen Tipp - oder ist das ne Sackgasse? Überseh ich was? Hammer

Danke nochmal.

12.01.2010, 10:46

Kühlkiste

Auf diesen Beitrag antworten »

Zitat:

Original von tardezyx
Hallo nochmal,

@ Arthur

Wieso sollte ich mit 0 und 1 anfangen? Der Beweis soll doch allgemein sein und die Induktionsbehauptung gilt eh nur für

$\begin{eqnarray*} n\geq 2 \end{eqnarray*}$

Die zu beweisende Behauptung lautet:

$\begin{eqnarray*} a_n = \frac 15 ( 2^{n+2} + (-3)^{n} ) \ \mbox{für alle} \ n\in\mathbb N. \end{eqnarray*}$

Du kannst den Induktionsschritt z.B. von $\begin{eqnarray*} (n-1,n)\rightarrow (n+1) \end{eqnarray*}$ durchführen. Also muss der Induktionsanfang auch für (0, 1) geschehen.

Zitat:

Original von tardezyx
@ Bernd

Die Induktionsbehauptung ist doch diese fertige Formel:

$\begin{eqnarray*} a_{n} = \frac{1}{5} * ( 2^{n+2} + (-3)^{n} ) \end{eqnarray*}$

Dann gilt:

$\begin{eqnarray*} a_{n+1}=6a_{n-1}-a_n \end{eqnarray*}$

Und es müsste sich das ergeben:

$\begin{eqnarray*} a_{n+1}=\frac{6 * ( 2^{n+1} + (-3)^{n-1} ) - ( 2^{n+2} + (-3)^{n} )}{5} \end{eqnarray*}$

Ausmultiplizieren ist hier m.W.n. unmöglich.

Muss ich nun also die Induktionsbehauptung so umformen, dass ich auf eben diesen Term komme (wüßte nicht, wie das gehen soll)?

Danke & Gruß!

Deine Induktionsvoraussetzungen (IVs) lauten:

$\begin{eqnarray*} a_{n-1} = \frac 15 ( 2^{n+1} + (-3)^{n-1} ) \end{eqnarray*}$

und

$\begin{eqnarray*} a_{n} = \frac 15 ( 2^{n+2} + (-3)^{n} ). \end{eqnarray*}$

Auf Basis dieser Voraussetzung musst Du nun zeigen, dass:

$\begin{eqnarray*} a_{n+1}=6a_{n-1}-a_n. \end{eqnarray*}$

Dein Term oben lässt sich sehr wohl weiter umformen:

$\begin{eqnarray*} 6a_{n-1}-a_n\underbrace{=}_{IVs}\frac{6 \cdot ( 2^{n+1} + (-3)^{n-1} ) - ( 2^{n+2} + (-3)^{n} )}{5}\\ =\frac{ (3\cdot 2\cdot 2^{n+1} - 2 \cdot (-3)\cdot (-3)^{n-1} ) - ( 2^{n+2} + (-3)^{n} )}{5} = \ldots \end{eqnarray*}$

12.01.2010, 11:43

tardezyx

Auf diesen Beitrag antworten »

Danke!

Habs jetzt geraffelt... ich brauche den 2. Vorgänger (und nicht wie üblich den 1. Vorgänger) als Induktionsvoraussetzung und dann hauts hin.

Tanzen

Danke auch für die Darstellung der Aufsplitterung, so dass ich die Potenzen zusammenfassen kann. Das war irgendwo ganz hinten im Gehirnkasten abgelegt, dass sowas überhaupt geht.

Gruß!

Neue Frage »

Antworten »

Vollständige Induktion mit 2 Vorgängern

Verwandte Themen