Komplexe Funktionsaufgabe

21.11.2005, 19:35	Master	Auf diesen Beitrag antworten »
Komplexe Funktionsaufgabe Die Aufgabe ist relativ komplex und deshalb komm ich damit gar nicht klar - leider: Sei $\begin{eqnarray} m\in \mathbb N ,m\neq0 \end{eqnarray}$ und für $\begin{eqnarray} n \in \mathbb N \end{eqnarray}$ sei [n] der Rest der Division von n durch m. Sei $\begin{eqnarray} k=\sum_{n=o}^r~ e_n 2^n \end{eqnarray}$ mit $\begin{eqnarray} e_n \in {0,1} \end{eqnarray}$ . Sei $\begin{eqnarray} a\in \mathbb N \end{eqnarray}$ und seien f(n) und g(n) rekursiv definiert durch: $\begin{eqnarray} g(0):=[a], f(0):=g(0)^{e_0} \end{eqnarray}$ $\begin{eqnarray} g(n+1):= [g(n)^2] \end{eqnarray}$ $\begin{eqnarray} f(n+1):=[f(n)g(n+1)^{e_{n+1}} \end{eqnarray}$ Beweisen sie, dass $\begin{eqnarray} f(r)=[a^k] \end{eqnarray}$ gilt. (e ist hier ein Epsilon, nicht die exp-Funktion..aber sollte man aus dem Zusammenhang ja auch sehen ) Wie fange ich da an?
23.11.2005, 20:07	IchDerRobot	Auf diesen Beitrag antworten »
Hallo Master, bei der Definition von f(n+1) hast du Typos drin (die "]" fehlt, und du meinst vermutlich "e_{n+1}" statt "e_n+1"), editierst du bitte deinen Beitrag? Das Verfahren erinnert mich an Potenzierung mittels Binärzerlegung des Exponenten, auch binäre Exponentiation genannt. Der Beweis sollte mit Induktion funktionieren. Dazu definierst du $\begin{eqnarray} k_j = \sum_{n=0}^j e_n 2^n \end{eqnarray}$ für 0 <= j <= r. Dann gilt nämlich $\begin{eqnarray} k_j = k_{j-1} + e_j 2^j \end{eqnarray}$ für 1 <= j <= r. Dann beweist du mit Induktion nach j: $\begin{eqnarray} f(j) = [a^{k_j}] \end{eqnarray}$ und $\begin{eqnarray} g(j) = [a^{(2^j)}] \end{eqnarray}$ für alle 0 <= j <= r. Robot

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »