Prove that $S$ is countably infinite

Question

Suppose we have the set $S\subset\mathbb{ N \times N}$ where $\mathbb N$ is the set of positive integers $\{1, 2,\ldots\}$ with the property: $S = \{\langle m, n \rangle\mid m \leq n\}$. Suppose $f\colon S \to N$ is defined as: $$f(\langle m, n \rangle) = \frac{{n(n - 1)}}{2} + m.$$ Prove that $S$ is countably infinite.

Proof sketch: In order to prove $S$ is countably infinite I have to prove $f$ is a bijection, that is, it is both an injection and a surjection. However I don't even know how to get started on the injection part, say, suppose $f(\langle m_{1}, n_{1}\rangle)=f(\langle m_{2}, n_{2}\rangle)$ then $\langle m_{1}, n_{1} \rangle=\langle m_{2}, n_{2}\rangle$.

Hope someone could help me with this, thanks!

Answer 1

Hint: Recall that $1+\ldots+n-1 = \frac{n(n-1)}2$, and divide into two cases: $m_1+n_1<m_2+n_2$ and $m_1+n_1=m_2+n_2$ (note that in the latter there are also two cases).

Answer 2

To prove that $S$ is countably infinite is enough to prove that is infinite (since $S\subset \mathbb{N} \times \mathbb{N}$ and $\mathbb{N} \times \mathbb{N}$ is countable). Since $(1,n) \in S, \ \forall n \in \mathbb{N}$ you are done.