Trying to understand how the first Hadamard gate in Deutsch–Jozsa algorithm works
After studying the maths behind it, I realized that a linear algebraic expression for a quantum state may not appear to be intuitive at first sight (or prehaps it is only to the not mathematically gifted ones like myself). 

Apparently, this is how the expression in the Wikipedia page is derived:

$$\begin{align} &amp;\frac{\left|0...0\right\rangle + \left|0...1\right\rangle + \left|1...1\right\rangle}{\sqrt2 ... \sqrt2} \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle)\\ =&amp;\sum^{n}_{x=0}\frac{1}{\sqrt{2^n}} \left|x\right\rangle \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle) \\=&amp;\sum^{n}_{x=0}\frac{1}{\sqrt{2^{n+1}}} \left|x\right\rangle \cdot (\left|0\right\rangle - \left|1\right\rangle) \\ =&amp;\frac{1}{\sqrt{2^{n+1}}} \sum^{n}_{x=0} \left|x\right\rangle (\left|0\right\rangle - \left|1\right\rangle) \end{align}$$

Now this explains why it is alright to have the four $\frac{1}{\sqrt{2^{3}}}$ probability amplitudes above, which is indeed just the product of $\frac{1}{\sqrt{2^{2}}}$ and $\frac{1}{\sqrt{2}}$. 

$\frac{\left|0...0\right\rangle + \left|0...1\right\rangle + \left|1...1\right\rangle}{\sqrt2 ... \sqrt2} \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle)$ sure feels like we are having a superposition state within a superposition state (I'm not sure if that is the correct way to interpret it). And this is probably what makes an entangled system so magical when it comes to computation.