Geschlossene Formel für rekursive Definition

02.01.2018, 22:32	Mächtigkeit01	Auf diesen Beitrag antworten »
Geschlossene Formel für rekursive Definition Meine Frage: Hallo, ich habe Probleme damit systematisch eine geschlossene Formel für folgende rekursive Definition zu finden: x(k+1) = 2x(k) + 1 Meine Ideen: Durch wildes herumprobieren bin ich zwar auf eine Darstellung gekommen, aber wie kann man das systematisch machen? LG Gero
02.01.2018, 23:24	sibelius84	Auf diesen Beitrag antworten »
Hallo Mächtigkeit01, so "wild" ist dein Herumprobieren gar nicht! Du hattest schlussendlich Erfolg, das ist das Wichtige. Und so unsystematisch sieht es auch nicht aus. Würde ich durchaus zum Nachmachen empfehlen Eine systematische Herangehensweise ist die der erzeugenden Funktionen, indem du von beiden Seiten die Potenzreihe bildest: $\begin{eqnarray} (1) \qquad \sum_{k=0}^\infty x_{k+1}z^k = \sum_{k=0}^\infty (2x_k+1)z^k \end{eqnarray}$ . Ziel ist es nun, die erzeugende Funktion $\begin{eqnarray} X(z)=\sum_{k=0}^\infty x_kz^k \end{eqnarray}$ konkret zu bestimmen, um daraus eine explizite Formel für die x_k zu gewinnen. Also schreiben wir obige Gleichung ein wenig um: $\begin{eqnarray} (2)\qquad\frac 1 z \sum_{k=0}^\infty x_{k+1}z^{k+1} = 2X(z) + \sum_{k=0}^\infty z^k \end{eqnarray}$ . Links indizieren wir die Summe um, fügen x_0 hinzu, schreiben zu X(z) um und ziehen x_0 anschließend wieder ab; rechts verwenden wir die Summenformel für die geometrische Reihe. Das ergibt $\begin{eqnarray} (3)\qquad\frac 1 z \left(X(z)-x_0\right) = 2X(z) + \frac{1}{1-z} \end{eqnarray}$ . Wenn man dies nach X(z) umstellt und die erzeugende Funktion, die dann dort steht, wieder in eine Potenzreihe entwickelt, hat man eine konkrete Formel für die x_k. Man muss ein wenig aufpassen mit den Startwerten, denn diese einzubauen, kann manchmal ein wenig haarig werden. LG sibelius84
03.01.2018, 09:47	HAL 9000	Auf diesen Beitrag antworten »
Weniger systematisch, aber im vorliegenden einfachen Fall naheliegend wäre folgendes Vorgehen: Wegen $\begin{align} x_{k+1} + 1 = 2(x_k + 1) \end{align}$ hat man für die "verschobene" Folge $\begin{align} y_k = x_k + 1 \end{align}$ die Eigenschaft $\begin{align} y_{k+1} = 2y_k \end{align}$ , was zur geometrischen Folge $\begin{align} y_k = C\cdot 2^k \end{align}$ führt, und damit $\begin{align} x_k = C\cdot 2^k-1 \end{align}$ . Für $\begin{align} k=0 \end{align}$ ergibt das $\begin{align} C=x_0+1 \end{align}$ und damit genau die von dir gefundene Darstellung.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »