Vollständige Induktion - Problem mit Induktionsschritt

20.04.2010, 07:54

Graf_Love

Vollständige Induktion - Problem mit Induktionsschritt

Vorab: Das Prinzip und auch das Anwendungsverfahren der vollst. Induktion ist mir denke ich durchaus klar.

Ich habe eine Rekursive Folge:
$\begin{eqnarray*} h_1 = 2 h_2 = \frac{3}{2} h_{k}=h_{k-1}-\frac{1}{2}*(h_{k-1}-h_{k-2}+\frac{1}{2}) \end{eqnarray*}$
bzw.
$\begin{eqnarray*} h_{k} = \frac{3}{2}h_{k-1}-\frac{1}{2}h_{k-2}-\frac{1}{4} \end{eqnarray*}$
Die habe ich in eine iterative Form gebracht, weil die Aufgabenstellung es verlangte:

für k > 2:

$\begin{eqnarray*} h_k = \frac{(k-1)^2+(4-k)}{2^{k-2}} \end{eqnarray*}$

Nun soll ich diese via vollst. Induktion verifizieren - doch das kann ich nicht, weil ich auf beiden Seiten unterschiedliche Ergebnisse erhalte!

Induktionsanfang mit k=3 geht natürlich, aber der Induktionsschritt k -> k+1

funktioniert nicht!
Was ich mache:
Ich nehme $\begin{eqnarray*} h_{k+1} = \frac{3}{2}h_{k}-\frac{1}{2}h_{k-1}-\frac{1}{4} \end{eqnarray*}$ , setze dort jeweils die iterative Formel ein
und vereinfache dies auf
$\begin{eqnarray*} -2k+6=-2^{k-3} \end{eqnarray*}$ , was aber nicht dasselbe ist!

Wo liegt mein Fehler? :-(

20.04.2010, 08:46

klarsoweit

Auf diesen Beitrag antworten »

RE: Vollständige Induktion - Problem mit Induktionsschritt

Zitat:

Original von Graf_Love
$\begin{eqnarray*} h_{k} = \frac{3}{2}h_{k-1}-\frac{1}{2}h_{k-2}-\frac{1}{4} \end{eqnarray*}$

Mit einem Wort: falsch.

20.04.2010, 09:21

Kühlkiste

Auf diesen Beitrag antworten »

RE: Vollständige Induktion - Problem mit Induktionsschritt

Zitat:

Original von Graf_Love
Wo liegt mein Fehler? :-(

Hier passt nichts zusammen!
Du gibst zwei verschieden rekursive Darstellungen an, die beide nicht zur expliziten Darstellung passen. unglücklich

Solltest Du noch immer an Hilfe interessiert sein, dann poste bitte unbedingt die genaue Aufgabenstellung im exakten, originalen und ungekürzten Wortlaut!

20.04.2010, 10:42

Graf_Love

Auf diesen Beitrag antworten »

RE: Vollständige Induktion - Problem mit Induktionsschritt
Sorry, habe mich vertippt!
Die rekursive Folge ist
$\begin{eqnarray*} h_1 = 2 h_2 = \frac{3}{2} h_{k}=h_{k-1}-\frac{1}{2}+\frac{1}{2}*(h_{k-1}-h_{k-2}+\frac{1}{2}) \end{eqnarray*}$
(man beachte das -1/2 )

Die Originalaufgabenstellung dazu ist:

"Gewinnen Sie mittels vollständiger Induktion eine nicht rekursive Darstellung für h_k (also unabhängig von h_{k-1}." verwirrt

EDIT: Daher dann auch das $\begin{eqnarray*} h_{k} = \frac{3}{2}h_{k-1}-\frac{1}{2}h_{k-2}-\frac{1}{4} \end{eqnarray*}$
und die nicht-rekursive Darstellung
für k > 2:
$\begin{eqnarray*} h_k = \frac{(k-1)^2+(4-k)}{2^{k-2}} \end{eqnarray*}$

Wie oben bereits geasagt klappt jedoch leider mein induktionsschritt nicht :-/

20.04.2010, 10:46

Graf_Love

Auf diesen Beitrag antworten »

RE: Vollständige Induktion - Problem mit Induktionsschritt
Bitte löschen, unbeabsichtigter Doppelpost!

20.04.2010, 11:30

Kühlkiste

Auf diesen Beitrag antworten »

RE: Vollständige Induktion - Problem mit Induktionsschritt

Zitat:

Original von Graf_Love
"Gewinnen Sie mittels vollständiger Induktion eine nicht rekursive Darstellung für h_k (also unabhängig von h_{k-1}." verwirrt

Das kann auch nicht klappen!

Keine Ahnung wie Du an Deine 'nicht-rekursive Darstellung' gelangst.
Von der solltest Du Dich jedenfalls schleunigst verabschieden.

Versuch's doch mal mit:

$\begin{eqnarray*} h_n:=\frac{5-n}2,~n\in\mathbb N \end{eqnarray*}$

20.04.2010, 12:23

WebFritzi

Auf diesen Beitrag antworten »

RE: Vollständige Induktion - Problem mit Induktionsschritt

Zitat:

Original von Graf_Love
"Gewinnen Sie mittels vollständiger Induktion eine nicht rekursive Darstellung für h_k (also unabhängig von h_{k-1}." verwirrt

Wie soll das denn bitte gehen? Mit der vollst. Induktion kann man höchstens zeigen, dass eine gegebene explizite Darstellung die gleiche Folge definiert. Man kann so aber keine solche gewinnen. Das geht z.B. mithilfe von ein wenig linearer Algebra. So hat man auch (relativ spät in der Geschichte) eine explizite Darstellung für die Fibonacci-Zahlen gefunden.

20.04.2010, 14:25

Mystic

Auf diesen Beitrag antworten »

RE: Vollständige Induktion - Problem mit Induktionsschritt
Naja, ich könnte mir hier durchaus vorstellen, dass man mit "vollständiger Intuition" zunächst die Angabe umformt zu

$\begin{eqnarray*} h_k-h_{k-1}+\frac 12=\frac 12 (h_{k-1}-h_{k-2}+\frac 12) \ (k>2), \quad h_2-h_1+\frac 12 =0 \end{eqnarray*}$

daraus eine gewisse Vermutung ableitet (welche wohl?), diese dann mit vollständiger Induktion beweist, usw.

20.04.2010, 15:38

Kühlkiste

Auf diesen Beitrag antworten »

RE: Vollständige Induktion - Problem mit Induktionsschritt
Zur Vervollständigung...

Aus

$\begin{eqnarray*} a_0=2,~a_1=\frac 32,~a_{n+2}=\frac 32 a_{n+1}-\frac 12a_n-\frac 14 \end{eqnarray*}$

folgt zunächst:

$\begin{eqnarray*} \sum_{n=0}^\infty a_nx^n=\frac{4-5x}{2(1-x)^2}. \end{eqnarray*}$

Und die rechte Seite hat die Reihenentwicklung:

$\begin{eqnarray*} \frac{4-5x}{2(1-x)^2}=\frac 2{1-x}-\frac x{2(1-x)^2}=2\sum_{n=0}^\infty x^n-\frac x2 \sum_{n=0}^\infty (n+1)x^n= \sum_{n=0}^\infty\frac{4-n}2 x^n. \end{eqnarray*}$

Koeffizientenvergleich liefert nun das Ergebnis.

Neue Frage »

Antworten »

Vollständige Induktion - Problem mit Induktionsschritt

Verwandte Themen