Define f: ℕ×ℕ→ℕ as follows: For each (m,n) ∈ ℕ×ℕ, $\displaystyle f(m,n) =2^{m-1}*(2n-1) $

Prove that f is an injection.

I don't know how to go about doing this one.

Printable View

- Apr 23rd 2010, 03:52 PMdwsmith[SOLVED] Relations
Define f: ℕ×ℕ→ℕ as follows: For each (m,n) ∈ ℕ×ℕ, $\displaystyle f(m,n) =2^{m-1}*(2n-1) $

Prove that f is an injection.

I don't know how to go about doing this one. - Apr 23rd 2010, 05:52 PMDrexel28
Suppose that $\displaystyle f(m,n)=f(m',n')$, then we'd have that $\displaystyle 2^{m-1}(2n-1)=2^{m'-1}(2n'-1)$.

So let me ask you this, we can assume WLOG that $\displaystyle m\leqslant m'$, right? So this means that $\displaystyle m'-1-(m-1)=m'-m\geqslant 0$ and so dividing through we get $\displaystyle 2^{m'-m}(2n-1)=2n'-1$. Now, if $\displaystyle m'-m>0$ what would the problem be with that?__Spoiler__: - Apr 23rd 2010, 06:03 PMdwsmith
- Apr 23rd 2010, 06:04 PMDrexel28
- Apr 23rd 2010, 06:05 PMdwsmith
- Apr 23rd 2010, 06:07 PMDrexel28
- Apr 23rd 2010, 06:08 PMdwsmith
- Apr 23rd 2010, 06:09 PMDrexel28
- Apr 23rd 2010, 06:10 PMdwsmith
The left is even and the right is odd.

- Apr 23rd 2010, 06:12 PMDrexel28
- Apr 23rd 2010, 06:14 PMdwsmith
- Apr 23rd 2010, 06:16 PMDrexel28
- Apr 23rd 2010, 06:20 PMdwsmith
- Apr 23rd 2010, 06:21 PMDrexel28
[QUOTE=dwsmith;499960]Well if it equals zero, the left is odd and the right is odd. [quote]

Which is good!

Quote:

If it is >0, the right is even and the left is odd.

So...it must be true that?! - Apr 23rd 2010, 06:24 PMdwsmith
[quote=Drexel28;499961][quote=dwsmith;499960]Well if it equals zero, the left is odd and the right is odd.

Quote:

Which is good!

Which is bad!

So...it must be true that?!