1
$\begingroup$

Question

Pretty basic problem here. Looking for some guidance on my train of thought.

Give a recursive definition for the following set:

the set of positive integers not divisible by 5

My Attempt

First thing I did was create a bit of the set $$S (1,2,3,4,\;\;6,7,8,9,\;\;11,12,13,14,\dots).$$ As for a base case, I can say that 1 is in set $S$.

As for the inductive step, I ask myself "am I noticing a pattern to this set"? Yes. if $X/5 \not= 1$, then $X$ is in set $S$. That doesn't seem helpful to me though.

I figure I might as well take a look at the set lists. I know I need to use the previous term to get the next term, but there's a problem when I get to $S(4)$ that doesn't follow in suit.

$$S0 = (1)$$

$$S1 = S0 + 1 = 2$$

$$S2 = S1 + 1 = 3$$

$$S3 = S2 + 1 = 4$$

$$S4 = S3 + 2 = 6$$

Well shoot, doing this hasn't really gotten me anywhere either.

I thought I might try something similar to part c, and I really feel like whats provided here is close to what I need, but I just can't make the connection.

Do you think I should have multiple base cases? Perhaps a base that states 1 2 3 and 4 are all in set $S$ to start?

$\endgroup$
2
  • $\begingroup$ Think I may have figured something out. If I make 4 base cases 1 is in S, 2 in S, 3 in S, and 4 in S, then can I make the recursive definition "If X is in S, then X+5 is in S." That would make it so that no number is divisible by 5, but anything else is allowed... $\endgroup$
    – Podo
    Feb 27, 2017 at 6:56
  • $\begingroup$ I think the below answer will be helpful to you. However, I am thinking if you can use a little more complex notation and maybe resurrect this with just one base case. $\endgroup$ Feb 27, 2017 at 6:59

2 Answers 2

2
$\begingroup$

Let $s_1 = 1, s_2 =2, s_3 = 3, s_4 = 4$. Define $s_i = s_{i-4} +5, i > 4$.

$\endgroup$
2
  • $\begingroup$ So it does need the 4 base cases. $\endgroup$
    – Podo
    Feb 27, 2017 at 7:05
  • $\begingroup$ It doesn't need but it makes it nicer. I'll post a not so good answer with only one base case for comparison. But this answer is better than mine will be. $\endgroup$
    – fleablood
    Feb 27, 2017 at 8:12
1
$\begingroup$

Let $s_1 = 1$. For $i \ge 0$, Let $s_{i+1} = s_i + 1$ if $s_i \not \equiv 4 \mod 5$. Else let $s_{i+1} = s_i + 2$.

$\endgroup$
2
  • $\begingroup$ Or are conditional branches not allowed? $\endgroup$
    – fleablood
    Feb 27, 2017 at 8:16
  • $\begingroup$ No limitations on the answer, this would also be correct using only one base case. Was playing around to try and figure out what that looked like, but you beat me to it. Thanks for this mate! $\endgroup$
    – Podo
    Feb 27, 2017 at 8:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .