# How to prove by induction that $A = \left\{n \in\mathbb N | n=\frac{(a+b)(a+b+1)}{2}+a \land {a,b} \in \mathbb N\right\}?$ [closed]

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.

## closed as off-topic by user1729, Alex Provost, Abcd, RRL, Lee David Chung LinMar 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.

• – lhf Mar 12 at 13:56
• What have you tried? Do you know what induction is? – jgon Mar 12 at 14:06

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?

UPDATE

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
• I got to this point and I dont really know how to contunue... – KIMKES1232 Mar 12 at 13:34
• @KIMKES1232 can you continue with the update? – gt6989b Mar 12 at 13:38
• how can you just choose "let a......" ? – KIMKES1232 Mar 12 at 13:58
• @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... – 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.

Note:

$$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
• thank you!!!!!!! – KIMKES1232 Mar 12 at 14:24
• I would have much preferred for the OP to do some work himself... – gt6989b Mar 12 at 14:51