Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Aufgabensammlung: Lösung zu

Aufgabe 854: Explizite Darstellung von Funktionswerten einer rekursiv definierten Funktion

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Die Funktion $ \mbox{$f:\mathbb{N}\longrightarrow \mathbb{R}$}$ sei rekursiv definiert durch die Anfangsbedingungen $ \mbox{$f(0)=-1$}$, $ \mbox{$f(1)=1$}$, und durch die Rekursionsgleichung

$ \mbox{$\displaystyle f(n) \; =\; -3 f(n-2) + 4 f(n-1)\; . $}$
Finde eine explizite Formel für $ \mbox{$f(n)$}$ und beweise diese.

Die ersten Werte der Funktion $ \mbox{$f$}$ lauten $ \mbox{$-1,1,7,25,79$}$. Daraus kann man die Vermutung $ \mbox{$f(n)=3^n - 2$}$ ableiten. Wir beweisen diese Formel durch Induktion.

Induktionsanfang: $ \mbox{$f(0)=-1=3^0 - 2$}$.

Induktionsschritt: Wir nehmen an, die Formel stimmt für alle $ \mbox{$m$}$ mit $ \mbox{$0\leq m<n$}$. Wir müssen zeigen, daß sie auch für $ \mbox{$n$}$ gilt.

Fall $ \mbox{$n = 1$}$. Hier gilt die Formel, es ist $ \mbox{$f(1) = 1 = 3^1-2$}$. (Diesen Fall kann man auch als Teil des Induktionsanfangs sehen.)

Fall $ \mbox{$n\geq 2$}$. Nun haben wir nach Induktion die Gültigkeit der Formel für $ \mbox{$n-2$}$ und $ \mbox{$n-1$}$ zur Verfügung. Wir erhalten

$ \mbox{$\displaystyle \begin{array}{rcl} f(n) & = & -3f(n-2) + 4f(n-1)\\ & =... ... = & -3^{n-1} + 6 + 4\cdot 3^{n-1} - 8\\ & = & 3^n - 2\; . \\ \end{array}$}$
(Autoren: Künzer/Martin/Nebe)
[Zurück zur Aufgabe]
  automatisch erstellt am 7.  6. 2005