1

Define a set X of integers recursively as follows:

Base: 5 is in X

Rule 1: If x is in X and x>0, then x+3 is in X

Rule2: If x is in X and x>0, then x+5 is in X

Show that every integer n>7 is in X

I am pretty new to this stuff and I am very lost on this. Please help!

CaliforniaIsMyHome
  • 13
  • Is $9$ in your set $X$? – Santana Afton Apr 30 '17 at 07:44
  • Base: 5 is in X. Fine. Rule 2: 5 is in X so 8,11,14, 5+3k for positive k is in X. Rule 2; 5,10,15, and all 5+5k, and as 5+3k is in X then 5 + 3k + 5j and.... Actually, I don't think you can show 9 is in X. But any n > 8, is just a matter of showing n = 5 + 3k + 5j for some k and j. – fleablood Apr 30 '17 at 07:44
  • 3 and 5 are relatively prime. If you know some beginners number theory that can maybe help in showing for >10, but does not work for 9. – mathreadler Apr 30 '17 at 07:57
  • 9 and 12 can be proven. Was 3 in X? is so that all n >= 5 are in X – fleablood Apr 30 '17 at 07:57
  • @fleablood How did you get 9? – Santana Afton Apr 30 '17 at 08:00
  • That was a typo. You can not get 9 or 12. How did you get 12? – fleablood Apr 30 '17 at 08:08
  • The word "define" is not okay in this context. To make $X$ well-defined it should be added that $X$ (next to satisfying base and rules) is a subset of all sets of integers that satisfy base and rules. – drhab Apr 30 '17 at 08:15
  • Why do we make X well-defined? You are asked to prove what must be in $X$--- not that that is all that is in $X$. 7, 9, and -29.3 might be in $X$ but we'll never be able to prove it. Allowing $X$ to not be well-defined doesn't have anything to do with the problem and is just way over the head of the OP at this point. – fleablood Apr 30 '17 at 08:36
  • @fleablood I am not pleading for adding a clausule that makes $X$ well-defined, but for scratching the abused word "define". Here $X$ is no more than a set satisfying some conditions. – drhab Apr 30 '17 at 09:37

2 Answers2

1

Let $n \ge 13$. Divide $n$ by $5$ and take the remainder to get $n = k*5 + r$ and $k$ is at least $3$.

Case 0: if $r = 0$ then $n = 5+5+5+5 ..... = 5*k + 0 = n$ and $n $ is in $X$.

Case 3: if $r = 3$ then $n = 5+ 5+ 5+ .... + 3 = 5+ 3 + 5(k-1)$ is in $X$.

Case 1: if $r = 1$ then $n = 5+5+5+5+ ..... + 5 + 1 = 5+5+5+..... + 6 = 5(k-1)+3+3$ is in $X$

Can you do Case 2 and 4?

=====

This is a cute way.

Let $n = ......ba$ be the number written in digits. $a$ is the last digt and $b$ is the second to last digit.

If $a = 0$ or $5$ then $n = 5+5+5+5+..... $ for some number of $5$ so $n $ is in $x$.

If $a = 1$ or $6$ then $n = 5+5+5+5+ .... + 5 + 3+3$ for some number of $5$ so $n$ is in $X$ if $n \ge 11$.

If $a = 2$ or $7$ then $n = 5+5+5+5+ ..... + 5 + 3+3+3+3$ for some number of $5$ so $n$ is in $n$ if $n > 12$.

If $a = 3$ or $8$ then $n = 5+5+5+... + 3$ and $n$ is in $X$ for $n \ge 8$.

If $a = 4$ or $9$ then $n = 5+5+5+5 + .... + 3+3+3$ and $n$ is in $X$ for $n \ge 14$.

So all integers greater than $12$ are in $X$.

====

Ah, This is supposed to be a proof by induction! (I was worried that might be advanced.)

1: All numbers in the form $5k + 3j; k \ge 1; j \ge 0$ are in $X$.

Base case: It is true for $k = 1$ and $j=0$ as $5 = 5*1 + 0 \in X$.

Induction case: Assume it is true for $n = 5k + 3*0$. Then by Rule one it is true for $n = 5k + 3*0 + 5 = 5(k+1) + 3*0$. So it is true for all $n = 5k + 3*0$.

Assume it is true $n = 5k + 3j$. Then by Rule two it is true for $n = 5k + 3j + 3 = 5k + 3(j+1)$ . So it is true for all $n = 5k + 3j$.

2) Prove that for all $n\ge 13$ that $n = 5k + 3j$ for some $k \ge 1$ and $j \ge 0$ and either $k >1$ or $j > 2$.

Base case: $13 = 5*2 + 3$

Induction: If $n = 5k + 3j$ and $k > 1$ then$n+1 = 5(k-1) + 3(j+2)$ and $k \ge 1;j > 2$. If $n = 5k + 3j$ and $j > 2$ then $n+1 = 5(k+2) + 3(j-3)$ and $k >1; j \ge 0$.

So All $n \ge 13$ are $n = 5k + 3j$ for some $k \ge 1$ and $j \ge 0$ and either $k > 1$ or $j > 2$.

fleablood
  • 124,253
0

It cannot be shown.

$X=\{5,8\}\cup\{n\in\mathbb Z\mid n\geq10\}$ satisfies base and rules but does not contain $9$.

drhab
  • 151,093
  • Can you show that all integers greater than 10 can be expressed through this addition of 3 and 5? – Santana Afton Apr 30 '17 at 07:48
  • I haven't thought about that. You are asked to prove that $7\in X$ and I am only saying here that that cannot be done. Another question is: is set $X$ well-defined by base and rules? There might be more than one possibility. – drhab Apr 30 '17 at 07:57
  • It's provable for $n > 12$ as (by induction) if $n = 5k + 3j \in X$ then $n+1 = 5(k-1) + 3(j+2) = 5(k+2) + 3(j-3)\in X$ if either $k \ge 2$ or if $k = 1$ and $j \ge 3$. Which is the case for $n = 13 = 2*5 + 3$ – fleablood Apr 30 '17 at 08:12