Zeigen sie das diese Abbildung eine Bijektion ist: N x N → N f(m,n) = 2 hoch m (2n+1) -1?

Hey!

Zeigen Sie das die folgende Aufgabe eine Bijektion ist.

N x N → N f(m,n) = 2^m (2n+1) -1

Problem/Ansatz:

Beweise der Surjektivität.

∀ g ∈ N gibt es mindestens ein Paar (m,n) mit f(m,n) =g

Ich vermute, dass es surjektiv ist, da ich zu jeder probierten Zahl die ich für g eingesetzt habe ein Paar gefunden habe.

Nun weiß ich aber leider nicht wie ich, mein Wissen als Verallgemeinerung für diese Aufgabe, beweisen kann.

Ich bin dankbar über jede Hilfe !

Liebe Grüße

Answer 1

[eterneladam]

Du kannst doch jede Zahl eindeutig zerlegen in den "geraden Anteil" 2^m, d.h. die höchste Zweierpotzenz, die darin aufgeht, und den "ungeraden Anteil" 2n+1, das ist der Rest. Die "-1", um alles um eins nach Links zu schieben, braucht es wohl, weil N hier die Null enthalten soll: 2⁰(2*0+1)-1=0