Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Lexikon:

Rekursiv definierte 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 Übersicht

Sei $ \mbox{$f:\mathbb{N}\longrightarrow \mathbb{R}$}$ rekursiv definiert durch die Anfangswerte $ \mbox{$f(0) = 0$}$, $ \mbox{$f(1) = 1$}$, und durch die Rekursionsgleichung

$ \mbox{$\displaystyle f(n) \; =\; f(n-2) + f(n-1) + 2^{n-2} + 1\; . $}$
Zeige: $ \mbox{$f(n) = 2^n - 1$}$ für alle $ \mbox{$n$}$.

Lösung.

Beweis durch Induktion.

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

Induktionsschritt: Wir nehmen an, die Formel gilt für alle $ \mbox{$m$}$ mit $ \mbox{$0\leq m<n$}$. Dann gilt:

$ \mbox{$\displaystyle \begin{array}{rcl} f(n)&=&f(n-2)+f(n-1)+2^{n-2}+1\\ &=... ...}-1)+(2^{n-1}-1)+2^{n-2}+1\\ &=&2^{n-1}+2^{n-1}-1\\ &=&2^n-1. \end{array}$}$
(Autoren: Künzer/Martin/Nebe)
[Verweise]
  automatisch erstellt am 25.  1. 2006