2
$\begingroup$

I've been searching for an awnser but couldn't find anything satisfying. I have to use mathematical induction to prove the following:

Spivak's Calculus, chapter 2 question 9

Prove that if a set a $A$ of set of natural numbers contains $n_0$ and $k+1$ whenever it contains $k$, then $A$ contains all natural numbers $\ge n_0 $

Book's solution

Let $B$ be the set of all natural numbers $l$ such that $n_0 -1 + l$ is in A.; Then 1 is in $B$, and $l+1$ is in $B$ whenever $l$ is in $B$, so $B$ contains all natural numbers, which means that $A$ containts all natural numbers $\ge n_0$

My questions:

Here is what I understand:

I get that $l =1$ is in $B$ since $n_0 -1 +1 = n_0 -1 + 1 = n_0 \in A$

However I dont understand why they assume that $l+1$ is in B whenever $l$ is in $B$..

I would appreciate a lot if someone could give a complete explanation of this assumption and how can you prove that $l+1$ is in B and how it leads to proving the statement (the question)

Thank you so much and sorry If I made some english mistakes!

$\endgroup$
  • $\begingroup$ Seems like the proof would've been simpler than the book to say that since $n_0 \in A$, let $k=n_0$, so $n_0+1=n_1 \in A$. From there say: assume $n_i \in A$ then $n_i+1=n_{i+1} \in A$ as second step in induction. $\endgroup$ – Χpẘ Jul 28 '17 at 22:37
1
$\begingroup$

It follows from the assumption on the set $A$ that whenever $k$ is in $A$, then $k+1$ is in $A$.

In detail, assume that $l$ is in $B$. By definition of $B$, we have that $n_0-1+l$ is in $A$. Let $k=n_0-1+l$, so $k+1 = (n_0-1)+(l+1)$ is in $A$. By definition, this implies that $l+1$ is in $B$.

$\endgroup$
  • $\begingroup$ So simple.. thank you so much $\endgroup$ – Ian Leclaire Jul 28 '17 at 22:31
2
$\begingroup$

Note that whenever $k \in A$, $k+1 \in A$. As such, $n_0-1+l \in A$ implies $n_0+l \in A$. Therefore, $l+1 \in B$.

$\endgroup$
0
$\begingroup$

If $l\in B$ then $n_0-1+l\in A$. By definition of $A$ you can conclude that $n_0+l\in A$ and in the same form $n_0+l+1\in A$, this implies $l\in B$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.