Let $$A = \left\{ \frac{(a+b)(a+b+1)}{2}+a \mid {a,b} \in \mathbb N\right\} .$$ How do I prove that $A = \mathbb{N}$ ?

Induction seems to help. This is a way of proving that the set $\mathbb{N}^2$ is countable.

|cite|edit|reopen|undelete (1)|flag

deleted by user1729, user21820, RRL Mar 24 at 9:17

closed as off-topic by user1729, Alex Provost, Abcd, RRL, Lee David Chung Lin Mar 12 at 23:54

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – user1729, Alex Provost, Abcd, RRL, Lee David Chung Lin
If this question can be reworded to fit the rules in the help center, please edit the question.


HINT Set $f(a,b) = \dfrac{(a+b)(a+b+1)}{2}+a$ for all $a, b \in \mathbb{N}$. Thus, $A = \left\{ f(a,b) \mid a,b \in \mathbb{N}\right\}.$

Base Case. Let $a=b=0$ then $0 \in A$.

Inductive Step

Assume there exist $a,b \in \mathbb{N}$ such that $f(a,b) = n$ (which means $n \in A$). We need to prove that there exist $A,B \in \mathbb{N}$ such that $f(A,B) = n+1$ (which would imply $n+1\in A$).

Can you now finish the proof?


Let $A=a$ and $B = b+1$, then $$ f(A,B) = a + \frac{(a+b+1)(a+b+2)}{2} = a + \frac{(a+b)(a+b+1)}{2} + [\ldots] $$

Now let $A=a+b$ and $B=b$. Do the same. Then figure out how to tweak $A,B$ so the result is what you need...

A further hint is that $a,b$ in the fraction do not matter, only $a+b$ does, so if you add to $a$ and subtract from $b$ the same thing, the sum does not change...

deleted Mar 24 at 9:17
  • $\begingroup$ I got to this point and I dont really know how to contunue... $\endgroup$ – KIMKES1232 Mar 12 at 13:34
  • $\begingroup$ @KIMKES1232 can you continue with the update? $\endgroup$ – gt6989b Mar 12 at 13:38
  • $\begingroup$ how can you just choose "let a......" ? $\endgroup$ – KIMKES1232 Mar 12 at 13:58
  • $\begingroup$ @KIMKES1232 to prove $n+1 \in A$ you need to exhibit any $a,b \in \mathbb{N}$ such that $f(a,b) = n+1$. There is no restriction as to what they are... $\endgroup$ – gt6989b Mar 12 at 14:38

It is very convoluted but $A = \mathbb N$ means $A \subset \mathbb N$ and $\mathbb N \subset A$.

If $M\in A$ then there exist $a,b\in \mathbb N$ so that $\frac {(a+b)(a+b+1)}2 + a = M$. Either $a+b$ is even or $a+b+1$ is even. Either way $\frac {(a+b)(a+b+1)}2$ is an integer. So $M = \frac {(a+b)(a+b+1)}2 + a$ is an integer and as $a,b \ge 0$, $M \ge 0$ so $M \in \mathbb N$ and $A \subset \mathbb N$.

So we just need to prove $\mathbb N \subset A$ or in other words. If $n \in \mathbb N$ that there are $a,b\in \mathbb N$ so that $n =\frac {(a+b)(a+b+1)}2 + a$.

(Note: This must assume that $0$ is a natural number. If $a,b \ge 1$ then $\frac {(a+b)(a+b+1)}2 + a \ge 4$ and this isn't true.)

Proof by induction:

Base step: If $n = 0$ and $a=b=0$ we have $n=\frac {(a+b)(a+b+1)}2 + a$.

Inductive step:

If $n = \frac {(a+b)(a+b+1)}2 + a$ then $n+1 = \frac {(a+b)(a+b+1)}2 + (a+1)$

$= \frac {([a+1] + [b-1])([a+1]+[b-1])}2 + (a+1)$. $a \in \mathbb N$ so $a+1 \in \mathbb N$. If $b \ge 0$ then $b-1 \in \mathbb N$ and we are done.

However if $b = 0$ then we have $n = \frac {a(a+1)}2 + a$.

So $n+1 = \frac {a(a+1)}2 + (a+1) =$

$(a+1)(\frac a2 + 1) =$

$(a+1)(\frac {a + 2}2) =$

Let $a' = 0$ and $b' = a+1$ and we have $n + 1 = \frac {(a'+b')(a'+b' + 1)}2 + a'$ and we are done.


$1 + 2 + ..... + m = \frac {m(m+1)}2$.

It should be clear that for $n \in \mathbb N$ there is some $m$ so that $1+ 2 + .... + m \le n < 1 + 2 +.... + m + m+1$.

So $n = (1+2 + ... m) + k$ for some $k \le m$.

So $n = \frac {m(m+1)}2 + k$. Let $a = k$ and $b= m - k$ and ... we are done.

deleted Mar 24 at 9:17

for $n=0$ choose $a=b=0$, for $n=1$ choose $a=0,b=1$

Assume $$\frac{(a+b)(a+b+1)}{2}+a=n>0$$ As $n>0$, $a,b$ cannot both be zero

case $b=0$: (so $a>0$) $$\frac{((1)+(a-1))((1)+(a-1)+1)}{2}+(1)=n+1$$ case $b>0$: $$\frac{((a+1)+(b-1))((a+1)+(b-1)+1)}{2}+(a+1)=n+1$$

deleted Mar 24 at 9:17
  • $\begingroup$ thank you!!!!!!! $\endgroup$ – KIMKES1232 Mar 12 at 14:24
  • $\begingroup$ I would have much preferred for the OP to do some work himself... $\endgroup$ – gt6989b Mar 12 at 14:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.