1

Let $A$ be a set inside $\Bbb N^*$ that contains $1$ such that : $$i) ∀n ∈ A, 2n ∈ A$$ and $$ii) ∀n ∈ \Bbb N^* , n + 1 ∈ A ⇒ n ∈ A.$$

I was asked to show that $∀m ∈\Bbb N , 2^m ∈ A$ which was straightforward with induction but then I had to show that : $$A=\Bbb N^*$$ I tried using induction again, to show that $\Bbb N^*$ is included in $A$ thus the result, since this exercise is in the induction chapter but didn't get anywhere.

OUCHNA
  • 429
  • 1
    What does $\Bbb N^*$ denote? – John Hughes Jul 24 '20 at 15:56
  • Hint: Think about what property $(ii)$ is saying in words, and what the iteration of this property means. Suppose I know some large number like 1024 is in $A$. What can I conclude from property $(ii)$? – halrankard Jul 24 '20 at 16:00
  • 1
    $\Bbb N^*$ denotes positive integers excluding $0$ Im taught by the french. From that hint I can see that any large number in $A$ means any number less than that is also in $A$. I think im gonna try proof by contradiction thanks for the hint! – OUCHNA Jul 24 '20 at 16:14
  • What you describe is known as forward-backward induction. See, for example, here. – Batominovski Jul 24 '20 at 18:29

1 Answers1

1

$1\in A$ and the property (i) gives $\{2^n:n=0,1,2,3,\dots\}\subseteq A$.

Now the property (ii) gives that, $n\in A$ $\implies m\in A,\forall m\in\Bbb{N}^*$ such that $m\leq n$.

Now let $n\in \Bbb{N}^*$ then $n< 2^n\in A$. Which gives $n\in A$. Thus $\Bbb{N}^*\subseteq A$.