Question related to mathematical induction. Suppose that (i) $P(0)$ holds, and (ii) for all $n \in \mathbb{N}$, if $P(n)$ holds, then so does $P(n+3)$ and $P(2n + 1)$. What can we conclude? More precisely, let $S$ be the set of all natural numbers $n \in \mathbb{N }$ for which we can conclude from (i) and (ii) that $P(n)$ holds.
What is the set $S$ ?
I have found the numbers for which $P$ holds are : $$0, 1, 3,4,6,7,9,10,12,13,16,18,19...$$
Unable to view any pattern or something.
Can anyone give any insight or little hint?
Thank you.
 A: Your list is missing the number $15$ (which you can get to from $12$). With this added, it contains every number of the form $3k$ or $3k+1$. It is easy to show that (since you can get $P(0),P(1)$) it contains all such numbers. The more difficult part is to prove that these are the only numbers it contains; you can do this by showing that if $n$ is of the form $3k$ or $3k+1$ for some integer $k$ then so are $n+3$ and $2n+1$.
A: As long as you have 3 consecutive numbers for which the property is true, it is true for all integers above it. While looking at your sequence, it appears we are missing all the numbers congruent to 2 modulo 3. (Since we have 0 and 1 in the sequence, we have all the other numbers).
Adding 3 doesn't change the congruence modulo 3

*

*if n is congruent to 0 modulo 3, then 2n+1 is congruent to 1 modulo 3.

*if n is congruent to 1 modulo 3, then 2n+1 is congruent to 0 modulo 3.

We can conclude that if i) and ii) are true, then your property holds for all number that are congruent to either 0 or 1 modulo 3.
A: Well, certainly $P(3k)$ holds for any natural $k$, by repeated application of $P(n)\implies P(n+3).$ We can also conclude $P(3k+1)$ holds for any natural $k$, since $P(1)$ holds. Can you see why we can never conclude $P(3k+2)$ holds?
