Based on some notes I just read, I think I may have completely misunderstood the notion of constructing a sequence by induction. Here is one example from Rudin's book to illustrate it:
Let $S$ be a countable set and $E \subset S$ an infinite subset. Then $E$ is countable.
The proof I'd write, which is very similar to Rudin's is to say that because $S$ is countable I can write it as a sequence $S = \{s_1, s_2, \ldots\}$. Then because $E \subset S$, I can construct a subsequence inductively by letting $n_1$ be the minimal index for which $s_{n_1} \in E$, then $n_2 > n_1$ be the next smallest index for which $s_{n_2} \in E$, and having constructed $x_1, \ldots, x_{k-1}$ in this manner, choosing $n_k > n_{k-1}$ such that $x_{n_k} \in E$. This subsequence then induces a map $f: \mathbb{N} \to E$ sending $k \mapsto x_{n_k}$ which is surjective, which is necessary and sufficient for countability.
Based on what I read, however, I cannot construct an infinite sequence by induction. It only allows me to construct a sequence of some length $N$ for each $N$, and if $E$ is an infinite set, this doesn't work. I'm very confused, then, on how I can assert the existence of such a sequence. Is this really just the axiom of choice? If so, is the fact that I choose $x_k$ after having chosen $x_1, \ldots, x_{k-1}$ matter? (That is, should there be an "inductive step"?)
You can certainly construct a countable sequence by induction. We do this all the time (think about factorials, or the natural numbers themselves; defined recursively by adding 1 to the successor). Your algorithm effectively enumerates the elements of $E$.
The fact that constructing an infinite subsequence amounts to saying what the sequence looks like up to a finite number $N$ for each number $N$ is precisely the magic of induction.