Discrete Fourier Transform
Classical Discrete Fourier transform acts on a vector $(x_0, x_1, ..., x_{N-1}) \in C^N$ and maps it to vector $(y_0, y_1, ..., y_{N-1}) \in C^N$ according to the formula $$ y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} e^{\frac{2\pi ijk}{N}} x_j, $$ where $k = 0, 1, 2, ..., N-1$.
My understanding of this, is that we are expressing the same vector in new basis (which has the same amount of dimensions as the original one). Moreover, each coefficient standing by the vector from new basis depends on each coefficient from the original basis.
Quantum Fourier Transform
In Quantum Fourier Transform we consider vecotrs of length $N = 2^n$. So each coefficient is calculated as folows
$$ y_k = \frac{1}{2^{n/2}} \sum_{j=0}^{2^n - 1} e^{\frac{2 \pi ijk}{2^n}} x_j$$
Wiki page (https://en.wikipedia.org/wiki/Quantum_Fourier_transform) gives the following example:
Consider the quantum Fourier transform on 3 qubits. It is the following transformation:
$$ QFT:|x\rangle \ \rightarrow \frac{1}{\sqrt{2^3}} \sum_{j=0}^{2^3 - 1} e^{\frac{2 \pi ixk}{2^3}} |k\rangle$$
I can't grasp the correspondence between number of qubits $n$ needed to express quantum state and this $N = 2^n$. Nielsen and Chuang in their book "Quantum Computation and Quantum Information" also write, that "because we take $N = 2^n$ we have the basis $|0\rangle, |1\rangle, ..., |2^n-1\rangle$ which is computational basis for $n$ qubit quantum computer".
Can you explain me, why we change the basis from $|0\rangle, |1\rangle, ..., |N-1\rangle$ to $|0\rangle, |1\rangle, ..., |2^n - 1\rangle$? My intuition tels me, that we now operate on such vectors $(x_0, x_1, ..., x_{2^n - 1}) \in C^{2^n - 1}$, but I know this is wrong.