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]

Question

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.

Answer 1

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...

Answer 2

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.

Answer 3

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$$