MathePrisma Logo

Rekursive Folgen

Rekursive Folgen

Das Prinzip

Zugegeben, das weiß man nicht sofort.
Das folgende Verfahren liefert die Lösung.
(Es lässt sich bequem mit Freunden oder in der Klasse anwenden.)

"In der Kürze liegt die Würze" ist der Grundsatz jedes Mathematikers

1. Herunterhangeln
2. Hochhangeln
1. Schritt  
 Wenn du M(20) suchst, dann frage doch einfach jemanden nach M(19). bereits bekannt: M(10)=19
2. Schritt
 Wer M(19) selbst sucht, braucht jemanden, der M(18) kennt. M(11)=19+2=21
3. Schritt
 Jemand könnte dir M(18) nennen, wenn ihm irgendeiner M(17) gibt. M(12)=21+2=23
...
 ...(bis man auf einen bekannten Wert stößt. Dann kann man sich durch Weitergabe der Ergebnisse hochhangeln.) ...

Wer n hierbei zu groß wählt, verliert schnell seine Freunde. Deshalb müssen wir das Rezept noch etwas verfeinern.

Leicht zu sehen

n 1 2 3 4 ... n
M(n) M(1)=1 3 5 7 ... ungerade Zahlen
M(n) M(1)=1 M(1)+2 M(2)+2 M(3)+2 ... M(n-1)+2, n>1 rek. Darst.
M(n) 1 1+2 (1+2)+2 ((1+2)+2)+2 ... 1+2(n-1)

Definition
explizite Darstellung

Begriffsnetz

Man unterscheidet zwischen der rekursiven Darstellung
M(1)=1
M(n)=M(n-1)+2

und der expliziten Darstellung
M(n)=1+2(n-1)
der Folge.

Wir erinnern uns

Mit der expliziten Darstellung ist es möglich, jedes Folgenglied sofort auszurechnen.

\(\displaystyle \text{n} = 20 : \quad \text{M}(20) = \underbrace{\text{M}(19) + 2}_{\begin{array}{cc}\text{rekursive}\\ \text{Darstellung}\end{array}} = \underbrace{1 + 2 \cdot 19}_{\begin{array}{cc}\text{explizite}\\ \text{Darstellung}\end{array}} = \underline{39}\)


Die Gültigkeit der expliziten Darstellung beweist man leicht mit Hilfe der vollständigen Induktion.

Es ist am einfachsten rekursiv zu denken und explizit zu rechnen.

Deshalb:

  1. Verallgemeinere zuerst deine Denkschritte (rekursive Darstellung).
  2. Finde eine bequeme Vorschrift zum Rechnen (explizite Darstellung).

Alles klar?

Jetzt kannst du dein Wissen unter Beweis stellen.