You wrote:
i understand how to do ordinary induction proofs and i understand that strong induction proofs are the same as ordinary with the exception that you have to show that the theorem holds for all numbers up to and including some n (starting at the base case) then we try and show: theorem holds for $n+1$
No, not at all: in strong induction you assume as your induction hypothesis that the theorem holds for all numbers from the base case up through some $n$ and try to show that it holds for $n+1$; you don’t try to prove the induction hypothesis.
In your example the simple induction hypothesis that the result is true for $n$ is already enough to let you prove that it’s true for $n+1$, so there’s neither need nor reason to use a stronger induction hypothesis. The proof by ordinary induction can be seen as a proof by strong induction in which you simply didn’t use most of the induction hypothesis.
I suggest that you read this question and my answer to it and see whether that clears up some of your confusion; at worst it may help you to pinpoint exactly where you’re having trouble.
Added: Here’s an example of an argument that really does want strong induction. Consider the following solitaire ‘game’. You start with a stack of $n$ pennies. At each move you pick a stack that has at least two pennies in it and split it into two non-empty stacks; your score for that move is the product of the numbers of pennies in the two stacks. Thus, if you split a stack of $10$ pennies into a stack of $3$ and a stack of $7$, you get $3\cdot7=21$ points. The game is over when you have $n$ stacks of one penny each.
Claim: No matter how you play, your total score at the end of the game will be $\frac12n(n-1)$.
If $n=1$, you can’t make any move at all, so your final score is $0=\frac12\cdot1\cdot0$, so the theorem is certainly true for $n=1$. Now suppose that $n>1$ and the theorem is true for all positive integers $m<n$. (This is the strong induction hypothesis.) You make your first move; say that you divide the pile into a pile of $m$ pennies and another pile of $n-m$ pennies, scoring $m(n-m)$ points. You can now think of the rest of the game as splitting into a pair of subgames, one starting with $m$ pennies, the other with $n-m$.
Since $m<n$, by the induction hypothesis you’ll get $\frac12m(m-1)$ points from the first subgame. Similarly, $n-m<n$, so by the induction hypothesis you’ll get $\frac12(n-m)(n-m-1)$ points from the second subgame. (Note that the two subgames really do proceed independently: the piles that you create in one have no influence on what you can do in the other.)
Your total score is therefore going to be
$$m(n-m)+\frac12m(m-1)+\frac12(n-m)(n-m-1)\;,$$
which (after a bit of algebra) simplifies to $\frac12n(n-1)$, as desired, and the result follows by (strong) induction.
The implicit assumption here is that if
- $P(0)$ is true, and
- $P(a)$ is true implies that $P(a + 1)$ is true for any natural $a$,
then $P$ is true over all naturals (including $0$). Notice that replacing
\begin{align*}
P(a) \ \text{is true implies that} \ P(a + 1)
\end{align*}
with
\begin{align*}
P(a) \ \text{and} \ P(a + 1) \ \text{are true}
\end{align*}
results in a stronger assumption. So, if we have a proof that works with the stronger assumption, it still implies that $P$ is true over all naturals.
Usually, any proof using this stronger assumption would mean that the induction is redundant. But any proof of this problem that avoids using this inductive process results in having to use the fact that every natural has a predecessor, which is part of what we're trying to prove!
So, we can only use the fact that successors are defined. Then the proof looks like a traditional proof by induction because we're using the assumption mentioned at the beginning along with successor operators, both of which we happen to do in proofs by induction in general.
Put another way, this is a linguistic issue. The notion usually associated with the word "induction" is building up truth successively to prove that a statement is true over positive integers. This is the point that the hint is getting at, rather than strictly requiring that the induction hypothesis be used to show that $P(a) \implies P(a + 1)$ for any positive integer $a$.
Best Answer
The heart of the argument goes something like this.
Suppose that for some particular $n$ you have found $B = \{z_1, \ldots. z_n\} \subset A$ in $A$, where the $z_i$ are all different. That's an assertion about the number $n$. You want to show the same assertion is true for $n+1$. Well, by hypothesis $A$ is infinite. Since $B$ is finite, it can't be all of $A$, so you can find some element $a \in A$ that's not one of the $z_i$. Then define $z_{n+1} = a$.
What about the base case, to get the induction started? Well, since $A$ is infinite it's not empty, so you can choose some element $a \in A$ for the value $z_1$.
I think the reason you have trouble with this exercise is that so far what you've been taught about induction suggests to you that it's about equations. It's not, it's about statements about integers. Often but not always that statement asserts the truth of some equation involving an integer.
I recommend that you prove the inductive step first, and then the base case. That stresses the fact that what you are proving is that
Related: https://matheducators.stackexchange.com/questions/10021/why-are-induction-proofs-so-challenging-for-students/10057#10057