1

Prove by induction on n the following statement $$~∀~n ∈ Z \ge 0 ~~(~ ∃~x,~y ∈ Z~\ge 0~~ ( n = 0.5 ( x + y ) ( x + y + 1 ) + y ))~$$

I've managed to prove the base case of $~P(0)~$. However I'm stuck on the inductive cases. I've tried directly going to $~P(n+1)~$ but then I'll be stuck with

$$n + 1 = ( x + y ) ( x + y + 1 ) + y + 1$$

nmasanta
  • 9,222
CXY
  • 39
  • Bear in mind that the $x,y$ in your $P(n+1)$ case may differ from the $x,y$ in your inductive hypothesis (the $P(n)$ case). To avoid confusion, in the $P(n+1)$ case, I'd use $x',y'$ to denote the integers in question, or just different letters altogether. – PrincessEev Sep 29 '19 at 02:47
  • Please see https://math.meta.stackexchange.com/questions/5020/ It's also good to have your question in the question, rather than just in the title. – Angina Seng Sep 29 '19 at 03:18

1 Answers1

0

After you assume that $\exists x,y \in \mathbb{Z} \ge 0$ such that $$n=\frac{(x+y)(x+y+1)}{2} + y$$ you get that $$n+1 = \frac{(x+y)(x+y+1)}{2} + y + 1$$ If $x>0$, we can define $x'=x-1,y'=y+1$ (and $x',y'\in \mathbb{Z}\ge0)$ and we get that $$n+1=\frac{(x'+y')(x'+y'+1)}{2} + y'$$ and we are done.

If $x = 0$, we got that $$n+1=\frac{y(y+1)}{2} + y+1=\frac{y(y+1)+2(y+1)}{2} = \frac{(y+1)(y+2)}{2}$$
We can define $x' = y+1, y' = 0$ $$n+1=\frac{x'(x'+1)}{2} = \frac{(x'+y')(x'+y'+1)}{2} + y'$$
$$\Box$$

  • will x' be still within the domain of Z >= 0 ? What if my x then was 0, it will make x' = -1 wont it? – CXY Sep 29 '19 at 10:23
  • Yes, that's exactly the reason why I handled the case $x=0$ differently... –  Sep 29 '19 at 10:32
  • thank you! Just really difficult to know that you can denote x' as y+1 and y' as 0 – CXY Sep 30 '19 at 11:57