# Trying to understand how the first Hadamard gate in Deutsch–Jozsa algorithm works

I'm still a beginner in the quantum aspect of computer science (self-studying). So please bear with me if this may sound like a stupid question.

I know Hadamard gate transforms qubit into a superposition state with $\frac{1}{2}$ chance that the outcome would be 0 or 1 when the wave function collapses:

$$\frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt2} \text{ for }\left|0\right\rangle \\ \frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2} \text{ for }\left|1\right\rangle$$

For already-in-a-superposition qubit, it would be just some linear transformation.

$$\alpha\left|0\right\rangle + \beta\left|1\right\rangle \rightarrow \alpha \frac{\left|0\right\rangle + \left|1\right\rangle}{\sqrt2} + \beta \frac{\left|0\right\rangle - \left|1\right\rangle}{\sqrt2} = \frac{\alpha+\beta}{\sqrt2}\left|0\right\rangle + \frac{\alpha-\beta}{\sqrt2}\left|1\right\rangle$$

But I got really confused when I see the $\Sigma \left|x\right\rangle$ in the equation on the Wikipedia article about Deutsch–Jozsa algorithm.

A Hadamard transformation is applied to each bit to obtain the state

Why is it doing a summation with a ever-increasing value of $x$? My understanding of a qubit is that it can only be in either $\left|0\right\rangle$, $\left|1\right\rangle$ or a superposition state.

What the equation is doing above appears to indicate that if $n$ is 2, we would get

$$\frac{1}{\sqrt{2^{3}}} \left|0\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}}\left|1\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \\\frac{1}{\sqrt{2^{3}}} \left|2\right\rangle (\left|0\right\rangle - \left|1\right\rangle) + \frac{1}{\sqrt{2^{3}}} \left|3\right\rangle (\left|0\right\rangle - \left|1\right\rangle)$$

How do I make sense of the $\left|2\right\rangle$ and $\left|3\right\rangle$?

[Update]