Vtyjkyuk

I'm starting to study this book and I've come across a problem that I haven't been able to solve. I need to prove that the next function is injective.

$g: Arightarrowmathbb Z_+$ where $A=(x,y)inmathbb Z_+timesmathbb Z_+ : y leq x$

$g(x,y)=1over 2x(x-1)+y$

It seems that it can't be solved in a direct way, like: $f(x_1)=f(x_2) Rightarrow x_1=x_2$. I was thinking about doing it in an inductive way. First, defining a set $B=zinmathbb Z_+ :exists!(x,y)in A text such z=g(x,y)$ and then apply induction over B, but it seems that it fails with n + 1

I appreciate any help

Any time you have a problem that says, "Show that X is Y", the process is:

1. Look up the definition of Y in the textbook.


2. Note the necessary conditions.


3. Show that X satisfies the conditions.

I don't have that textbook at arm's reach, but I am guessing that it says something like:

A function $f colon A to B$ is injective if for all $a_1,a_2in A$, $f(a_1) = f(a_2) implies a_1 =a_2$.

(The “defined” word in a definition is always emphasized or put in bold face. That helps you find definitions for things.)

In your case, $g(x,y) = frac12x(x-1)+y$. So you need to show that for all $(x_1,y_1), (x_2,y_2)in A$, if $frac12x_1(x_1-1)+y_1 = frac12x_2(x_2-1)+y_2$, then $x_1=x_2$ and $y_1 = y_2$.

If you're interested in an induction proof, you might try to show these two things:

1. $f(x+1,y) > f(x,y)$ for all $x in mathbbZ_+$.


2. $f(x+1,y+1) > f(x,y)$ for all $x in mathbbZ_+$.

Consider:

$x=1$:

$g(1,1)=1$;

$x=2:$

$g(2,1) =2, g(2,2)=3;$

$x=3:$

$g(3,1) =4, g(3,2)=5, g(3,3)=6$.

$x=4$:

$g(4,1)=7, g(4,2)=8,g(4,3)=9, g(4,4)=10$.
................
................

Grouping : in ascending order of $x$ and $y$:

$(1)(2,3)(4,5,6)$
$(7,8,9,10)(11,12,13,14,15).........$

Now backwards, we find $g^-1(z)$:

Pick any number $z$, say $z=13$,

1) subtract $1$ from $z$, i.e.

$z-1= 13-1=12$.

2) Now find the largest $x$ such that

$(1/2)x(x-1) le z -1 $,

in our example:

$(1/2)x(x-1) le (13-1) =12$

$x=5$ qualifies, since

$(1/2)5(5-1)=10$;

then $y=3$ (Recall: we picked $13$).

1) Note: $g$ is surjective (why?)

2) $g$ is injective , the formula determines uniquely the corresponding $x$ and $y$ for $z in mathbb Z^+$.