Let \mathbb{N}^{\star}=\{1,2,3,\ldots\} and for every k ∈ \mathbb{N}^{\star} define
I_{k}=\{x\in\mathbb{N}^{*}\mid{\frac{1}{2}}k(k-1)\lt x\leqslant{\frac{1}{2}}k(k+1)\}.(a) Show that I_k has k elements and that \{I_{k}\mid k\in\mathbb{N}^{\star}\} is a partition of \mathbb{N}^{\star}.
(b) Define f:\mathbb{N}^{*}\times\mathbb{N}^{*}\to\mathbb{N}^{*} by
f(m,n)={\textstyle{\frac{1}{2}}}(m+n-2)(m+n-1)+m.Show that f(m,n)\in I_{m+n-1} and deduce that
f(p,q)\in I_{m+n-1}\Leftrightarrow p+q=m+n.Hence show that/is injective.
(c) For 1 ≤ r ≤ k show that f(r, k + 1 — r) ∈ I_{k} and deduce that f is also surjective.
(a) It is helpful to compute a few of the \,I_{k}. For example,
I_{1}=\{1\},\quad I_{2}=\{2,3\},\quad I_{3}=\{4,5,6\},\quad I_{4}=\{7,8,9,10\}.Now by the definition of \,I_{k} we have {\textstyle\frac{1}{2}}k(k+1)\in I_{k}\,\ {\mathrm{and}}\ {\textstyle\frac{1}{2}}k(k+1)-k= {\textstyle\frac{1}{2}}k(k-1)\not\in I_{k}. It is clear from this that \,I_{k} consists of the k elements
{\textstyle\frac{1}{2}}k(k+1)-k+1,\dots,{\textstyle\frac{1}{2}}k(k+1).Consequently we see that the \,I_{k} form a partition of \mathbb{N}^{\star}.
(b) We observe that
{\textstyle\frac{1}{2}}(m+n-2)(m+n-1)+m={\textstyle\frac{1}{2}}(m+n)(m+n-1)+1-nand that this belongs to I_{m+n-1} since the largest integer in I_{m+n-1} is \textstyle{\frac{1}{2}}(m+n)(m+n-1)\quad{\mathrm{and}}\quad I_{m+n-1} contains m+n-1 integers. Thus f(m,n)\in I_{m+n-1}.
Since f(p,q)\in I_{p+q-1}. and the \,I_{k}. from a partition, we have
f(p,q)\in I_{m+n-1}\Leftrightarrow I_{p+q-1}=I_{m+n-1}\\ \Leftrightarrow p+q-1=m+n-1\\ \Leftrightarrow p+q=m+n.To show that f is injective, suppose that f(p,\,q)=f(m,\,n). Then p + q = m + n and so
\begin{array}{c}{{\frac{1}{2}(p+q-2)(p+q-1)+p=f(p,q)}}\\ {{}}{{=f(m,n)}}\\ {{}}{{=\frac{1}{2}(m+n-2)(m+n-1)+m}}\\ {{}}{{=\frac{1}{2}(p+q-1)(p+q-1)+m.}}\end{array}Consequently we have that m=p, and hence also q = n. Thus (p, q) = (m, n) and so f is injective.
(c) We note that if 1\leqslant r\leqslant k then
f(r,k+1-r)\in I_{r+(k+1-r)-1}=I_{k}\,.But f is injective, \,I_{k} contains k elements, and there are k values of r; therefore we must have that every element of \,I_{k}. is the image of some element (r,k + 1 – r) under f. Since this is true for every \,I_{k}. in the partition, it follows that f is also surjective.