Proving a multi variable function bijective

Question

I understand the theory of how to prove a mutli variable function bijective, however I somehow can neither prove this function injective or surjective:

$$f: \mathbb N\times \mathbb N \rightarrow \mathbb N, (a, b) \mapsto {(a+b)}^{2} + a$$

I tried to start with $f(a, b) = f(a', b')$ but I don't really know how to continue from there. To prove it surjective I started with: show that for every $n$ there is $(a, b)$ with $f(a, b) = m$ but was not successful there either. To make matters worse I don't even know yet if this function is injective, surjective, neither or both. Any help would be appreciated!

Answer 1

It is helpful to arrange the values of $f(a,b)$ in a table, thus:

$$\begin{matrix} \vdots & \vdots & \vdots & \vdots \\ 9 & 17 & 27 & 39 & \cdots \\ 4 & 10 & 18 & 28 & \cdots \\ 1 & 5 & 11 & 19 &\cdots \\ 0 & 2 & 6 & 12 & \cdots \end{matrix}$$

Here we visualize the set of all $a,b \in \mathbf{Z}_{\geq 0}$ as the upper-right quadrant.

You can see that the entries along the $b$-axis are the squares $0,1,4,9$ and that as you move down and to the right the entries go up by exactly $1$. This shows that the function is injective but not surjective, and that the numbers it misses are precisely those between $a^2+a$ and $a^2+2a+1=(a+1)^2$ for each non-negative $a$ (once you prove that these patterns always hold; details below). Incidentally, it also shows that you could, by modifying the domain slightly, obtain a bijection from a subset of $\mathbf{Z}^2$ to $\mathbf{Z}_{\geq 0}$.

Details of the proof: observe that $$f(a+1,b-1)=(a+1+b-1)^2+a+1=(a+b)^2+a+1=f(a,b)+1$$ and that $$f(a,0)=a^2+a<a^2+2a+1=(a+1)^2=f(0,a+1)$$ for all $a \geq 0$.

Answer 2

The map is certainly not surjective, as it has been pointed out in the comments.

Let us try to prove injectivity. I will rewrite the function $(a+b)^2+a$ as $c^2+a$ where $c=a+b$, and in particular note $c\geq a$ because $b\in\mathbb{N}$. Argue by contradiction, suppose there exist $a, c, \hat{a}, \hat{c}$ with $c\neq \hat{c}$ and $a\neq \hat{a}$ such that $$ c^2+a=\hat{c}^2+\hat{a}, $$ noting the case $c=0$ and the case $\hat{c}=0$ are excluded because they would imply $a=b=\hat{a}=\hat{b}=0$.

Without loss of generality, let $c>\hat{c}$. Write $$ c^2=\hat{c}^2+\hat{a}-a, $$ and we try to prove the LHS is strictly larger than the RHS, deriving a contradiction. We prove it for the "best" case, $a=0$, which then proves it for $a>0$ as well. Thus we write $$ c^2=\hat{c}^2+\hat{a}, $$ and since $\hat{a}\leq \hat{c}$ the RHS is bounded above by $\hat{c}^2+\hat{c}$. We had $c>\hat{c}$; taking the best case scenario again we try $c=\hat{c}+1$, which yields $c^2=\hat{c}^2+2\hat{c}+1$, strictly larger than the upper bound on the RHS, which yields the contradiction.