zZ rekursive Funktion ist bijektiv

18.10.2012, 23:42

Crisp

zZ rekursive Funktion ist bijektiv

Hallo.
Wie beweise ich, dass eine rekursiv definierte Funktion bijektiv ist?
Sei f:A->B definiert durch f(0):=1 und f(a):= f(a-1) - C*a.

Ich habe Probleme dabei, da ich wenn ich f(p) = f(q) voraussetze, ich ja nicht darauf schließen kann, dass f(p-1)=f(q-1) ist, oder?

19.10.2012, 07:20

Leopold

Auf diesen Beitrag antworten »

Was soll $\begin{eqnarray*} f: A \to B \end{eqnarray*}$ in diesem Zusammenhang bedeuten? Von der Rekursionsvorschrift aus vermute ich rückwärts, daß $\begin{eqnarray*} A = \mathbb{N} = \{ 0,1,2,3,\ldots \} \end{eqnarray*}$ die Menge der natürlichen Zahlen (?) und $\begin{eqnarray*} C \end{eqnarray*}$ eine positive (?) reelle (?) Konstante ist. Bitte solche Nebenangaben immer mitteilen, die sind für das Verständnis des Ganzen wichtig.

Man könnte dann für $\begin{eqnarray*} f \end{eqnarray*}$ eine explizite Vorschrift angeben:

$\begin{eqnarray*} f(a) = 1 - \frac{1}{2} C a (a+1) \end{eqnarray*}$

Dazu muß man nur die Rekursionsvorschrift ein paar Mal anwenden und sich an die Formel für die Summe der ersten $\begin{eqnarray*} a \end{eqnarray*}$ natürlichen Zahlen erinnern. Aber das ist gar nicht nötig. Denn der Rekursionsvorschrift kann man direkt ansehen, daß $\begin{eqnarray*} f \end{eqnarray*}$ streng monoton fällt, denn vom vorigen Wert wird immer ein weiterer Wert subtrahiert. Den Monotonienachweis kann man natürlich auch mit einem formalen Induktionsbeweis führen.
Damit ist die Injektivität der Funktion offensichtlich. Bijektiv ist sie im strengen Sinn nur dann, wenn $\begin{eqnarray*} B \end{eqnarray*}$ gerade die Menge der Funktionswerte ist.

Irgendwie habe ich das Gefühl, daß diese Aufgabe ganz anders gemeint ist. Dazu müßte man allerdings den exakten (!) Aufgabentext haben.

19.10.2012, 12:01

Crisp

Auf diesen Beitrag antworten »

Sei f: N\{0} -> Z mit f(1):=0 und f(n+1)=f(n)-n*sgn((f(n))^n. Zeigen Sie, f ist bijektiv.

Meine Idee war, die Funktion in Fälle n=2k und n=2k+1 zu unterteilen und dann das Monotonieverhalten im Intervall [f(2k) ,f(2k+1)] und [f(2k+1),f(2(k+1))] zu zeigen...

Ich weiß was Injektiv und Surjektiv heißt, aber wie zeige ich jetzt bei einer solchen >>rekursiv<< definierten Funktion genau, dass sie bijektiv ist. Wenn ich so eine explizite Vorschrift finden würde, würde es schonmal einfacher sein.

19.10.2012, 12:42

RavenOnJ

Auf diesen Beitrag antworten »

Was ich nicht ganz verstehe: Nach der üblichen signum-Definition ist sgn(0) := 0, also sgn(f(1)) = sgn(0) = 0. Damit wird f(2) = 0, ebenso f(3) = 0 usw..

Gruß
Peter

19.10.2012, 13:30

Crisp

Auf diesen Beitrag antworten »

sgn (x) = -1, falls x<0;
1, falls x>=0.
Ich weiß, die übliche Definition ist anders, aber unser Informatik Professor ist da etwas eigen.

19.10.2012, 13:54

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Crisp
Sei f: N\{0} -> Z mit f(1):=0 und f(n+1)=f(n)-n*sgn((f(n))^n.

[...]

sgn (x) = -1, falls x<0;
1, falls x>=0.

Dann ist trotzdem $\begin{eqnarray*} f(4)=0 \end{eqnarray*}$ , und nichts ist mit der Bijektivität... unglücklich

Kann es sein, dass dieses ^n einfach nur weg muss, und die Iteration schlicht und einfach

$\begin{eqnarray*} f(n+1) = f(n) - n\cdot\operatorname{sgn}(f(n)) \end{eqnarray*}$

lautet. verwirrt

Neue Frage »

Antworten »

zZ rekursive Funktion ist bijektiv

Verwandte Themen