Gap in this proof of the Hahn–Banach theorem In section 13.4 of Introductory Real Analysis by Kolmogorov and Fomin, the Hahn–Banach theorem is proved. (pp.132–134 of the Dover edition.)  There seems to me to be a gap in the proof, which I suppose is due to my own confusion, but I hope someone can explain it to me.
K&F want to show that, given a linear functional $f_0$ defined on a subspace $L_0$ of a real linear space $L$, if certain conditions are satisfied then $f_0$ can be extended to a function on all of $L$.  They do this by choosing a vector $z$ in $L\setminus L_0$, then showing how to extend $f_0$ to the smallest subspace of $L$ that contains both $L_0$ and $z$.  This obviously suffices when $L$ is of finite dimension.
K&F then continue (page 134):

To complete the proof, suppose first that $L$ is generated by a countable set of elements $x_1, x_2, \ldots, x_n, \ldots$ in $L$.  Then we construct a functional on $L$ by induction, i.e., by constructing a sequence of subspaces $$L^{(1)} = \{L, x_1\}, \quad L^{(2)} = \{L^{1}, x_2\}, \ldots,$$ each contained in the next.  Here $\{L^{(k)}, x_{k+1}\}$ denotes the minimal linear subspace of $L$ containing $L^{(k)}$ and $x_{k+1}$.  This process extends the functional onto the whole space $L$, since every element $x\in L$ belongs to some subspace $L^{(k)}$.

Leaving aside what appears to be an obvious typo in the displayed formula (“$L^{(1)} = \{\color{maroon}{L}, x_1\}$” should be “$L^{(1)} = \{\color{maroon}{L_0}, x_1\}$”) this reasoning seems wrong to me.  “This process extends the function onto the whole space $L$” is true only if $L$ is finite-dimensional.
As a counterexample, consider the space $M$ of all bounded sequences of reals and let $L^{(i)}$ be the subspace of $M$ consisting of sequences that are zero from the $i$th element onward.  Then the process extends the function onto any finite-dimensional subspace of $M$ but not onto all of $M$, and K&F's claim that “every element $x\in L$ belongs to some subspace $L^{(k)}$” is patently false; take $x = \langle 1, 1, 1, \ldots\rangle$ for example.
The discussion continues with an application of Zorn's lemma to handle spaces with an uncountable basis: the subspaces of $L$ are partially ordered by inclusion, and if $f_0$ can be extended to any ascending chain of them then it can be extended to the maximum element of the chain.  This does take care of the countable case.  But it seems like a big hammer to use, and K&F give no indication that this additional argument might be required for a space of only countably infinite dimension.  
What parts of my discussion are mistaken?


*

*Is the induction step really sufficient, as K&F claim? 

*If so, why, and what is wrong with my bounded sequences counterexample?

*If the K&F proof really does have a gap, is there a way to fill it that requires less heavy machinery than the Zorn's lemma argument?

 A: First of all, this business with assuming $L$ is countably generated and then doing Zorn's Lemma seems weird. I would recommend reading the proof in Folland's real analysis book (which I would recommend on the whole).
So I think their induction step (under the assumption of $L$ being countably generated) is fine. The assumption is precisely formulated as "There exist a countable collection $\{x_n\}$ such that every $l \in L$ is a linear combination of some finite subcollection of $\{x_n\}$." This is why they say every $x \in L$ belongs to some subspace $L^{(k)}$. 
This is why your counterexample is not really a counterexample. The vector $(1,1,\dots)$ is not in any $L^{(k)}$ (and thus is not a finite linear combination of the vectors you described). 
What I wrote above is my best guess for what is going on. As I hinted at before, I'm not sure how necessary this part of the argument is for the Zorn's Lemma part, so I'm not sure exactly what they mean by "generated by a countable set of elements", but what I have above I have a strong feeling is correct. 
A: *

*The induction step is indeed sufficient. The important thing for that is however not that the family $\mathscr{F} =\{ x_i : i \in I\}$ such that the space $L$ is generated by $L_0$ and $\mathscr{F}$ is countable, the crucial point is that the index set $I$ is well-ordered. But of course countable sets are the most common families we can index by a well-ordered set without invoking choice. For every $i \in I$, let
$$L^{(i)} = \operatorname{span}\:\bigl(L_0 \cup \{ x_j : j < i\}\bigr).$$
Then, having a linear functional $f^{(i)} \colon L^{(i)} \to \mathbb{R}$ dominated by the sublinear functional $p \colon L \to \mathbb{R}$, we obtain a - possibly degenerate, but nonempty - closed interval $[a_i,b_i] \subset \mathbb{R}$ of values a linear extension of $f^{(i)}$ to $\operatorname{span} \: \bigl(L^{(i)} \cup \{x_i\}\bigr)$ can take at $x_i$ and still be dominated by $p$. (If $x_i \in L^{(i)}$ we of course have $a_i = b_i = f^{(i)}(x_i)$.) Since we can specify a rule to choose the value of the extension at $x_i$ - we can always take the smallest admissible value, or the largest, or the midpoint or whatever takes our fancy - this works without choice. Thus by transfinite induction we obtain an extension to the whole space $L$ that is still dominated by $p$.

*The point where the bounded sequence example fails is that this space is not countably generated (over $\mathbb{R}$), or, in view of the above, that we don't have (without invoking a bit of choice) a generating set indexed by a well-ordered set. The space generated by the "standard unit sequences" is the space $c_{00}(\mathbb{N})$ of sequences with only finitely many nonzero terms, and that is much smaller than $\ell^{\infty}(\mathbb{N})$. Recall that "$E$ is generated by $S$" means that every element of $E$ can be written as a linear combination of elements of $S$, and "linear comination" means only finitely elements of $S$ are involved in the representation of each $e\in E$ [we don't assume a topology on $E$, so series involving infinitely many nonzero terms don't make sense].

*Since uncountable sets with a natural well-ordering aren't ubiquitous, we do need a bit of choice for the Hahn-Banach theorem in general. But much less than Zorn's lemma. The ultrafilter lemma is sufficient to prove Hahn-Banach. But the Hahn-Banach theorem does not imply the ultrafilter lemma according to the wikipedia article. So it should be provable using even less choice. But I don't know how much choice is actually required to have the Hahn-Banach theorem. Probably Asaf Karagila and Andreas Blass (those are the two users here who immediately come to mind) know more about that. However, I see no issue in using Zorn's lemma, the well-ordering theorem, or whatever other equivalent to the full axiom of choice in a proof if that makes the proof clearer, simpler, or more accessible.
A: The earlier answers all hit the important points and answer my question, but I want to add this summary that connects it with what was happening in my head.


*

*My fundamental confusion was in not understanding the relation between “generated by” and “basis”.  Specifically, I thought it was possible that $S$ might generate $X$ without containing a (Hamel) basis for it.

*The proof is in two parts, and I correctly surmised that the first part was not sufficient to prove the theorem for the space $M$ of all bounded sequences.

*But I mistakenly thought that $M$ was countably generated, and that K&F were therefore claiming that the first part was sufficient for $M$.  But this is wrong.   For $M$ to be generated by some set $S$ would mean that it was the smallest linear space containing $S$.  It does contain the countable set $\{e_i\}$ that I mentioned, but it is not the smallest such space.  As Daniel Fischer pointed out, the space $c_{00}$ of all eventually-zero sequences is a linear space that is smaller.  His comment here was what turned on the light for me.

*I had a basic misunderstanding of how “generated by” behaves.  I had imagined that the space generated by a set $S$ would be the space of all possible combinations of elements of $S$.  But no, the set of all combinations of finite subsets of $S$ is also a linear space, and if $S$ is infinite, this space is smaller.  This is the motivation for the definition of a Hamel basis.
(The situation is analogous to that of  the direct sum and the direct product of a family of abelian groups.)
I said in a comment that “my list of vectors is not a basis for the set of
bounded sequences, but there is nothing in the proof that suggests
that the $x_i$ must constitute a basis”.  This exemplifies my original confusion.  I now understand that
if a space is generated by $S$, then $S$ must contain a Hamel basis for the space; I knew that $\{e_i\}$ did not contain a Hamel basis for $M$, but mistakenly thought that it generated $M$ anyway.

*Since every element of a countably generated space is a combination of a finite subset of the generators, the first part of the proof does suffice for countably generated spaces.
Thanks to everyone who helped me understand this better, especially Daniel Fischer and mathworker21.
