function: prove f(i,j)=i+(i+j-1)(i+j-2)/2 is a bijection  TOPIC_SOLVED

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.

function: prove f(i,j)=i+(i+j-1)(i+j-2)/2 is a bijection

Postby rubelpatel on Mon Oct 10, 2011 8:58 am

Consider a function f:N x N -> N where f(i,j)=i+(i+j-1)(i+j-2)/2. Prove that f is a bijection.
rubelpatel
 
Posts: 1
Joined: Wed Aug 03, 2011 6:49 am

Sponsor

Sponsor
 

Re: function: prove f(i,j)=i+(i+j-1)(i+j-2)/2 is a bijection  TOPIC_SOLVED

Postby nona.m.nona on Mon Oct 10, 2011 12:45 pm

rubelpatel wrote:Consider a function f:N x N -> N where f(i,j)=i+(i+j-1)(i+j-2)/2. Prove that f is a bijection.

To complete the proof, follow the usual method:

Show that the function is one-to-one by proving that, if f(x1)= y1 equals f(x2) = y2, then x1 equals x2.

Show that the function is onto by proving that, for any y in the image, you can find an x in the pre-image.

If you experience difficulties, kindly please reply with a clear statement of your work and reasoning so far. Thank you.
nona.m.nona
 
Posts: 254
Joined: Sun Dec 14, 2008 11:07 pm


Return to Discrete Math

cron