Why does the Hadamard act as $H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}}\sum_{y\ \in\{0,1\}^n}(-1)^{x_1y_1+···+x_ny_n}|y\rangle $? In quantum-information, we have been told that the Hadamard gate over $n$-qubits can be defined as:
$$H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}}\sum_{y\ \in\{0,1\}^n}(-1)^{x_1y_1+···+x_ny_n}|y\rangle  
\\= \mathbb C^2 \otimes ... \otimes \ \mathbb C^2 = \mathbb C^{2^n}, \text{ where 
}|x\rangle = |x_1,x_2,...,x_n\rangle $$
However, I do not have any intuition about how this is constructed from the single qubit Hadamard:
$$\frac{1}{\sqrt{2}}\begin{bmatrix}\begin{array}{rrrrrrrr} 1 & 1 \\ 1 & -1  \end{array}\end{bmatrix}.$$
I am trying to figure out, and it thought of an induction over $n$, but do not know how to do it. Could anyone provide any help of proof?
 A: You can use an argument by way of induction as has been linked in the comments; or you can see it intuitively:
$$H^{\otimes n} | x \rangle= H^{\otimes n} | x_1, x_2,...,x_n \rangle$$
$$=\big(H|x_1 \rangle\big) \otimes \big(H|x_2 \rangle\big) \otimes...\otimes \big(H|x_n \rangle\big)$$
$$=\big(\frac{1}{\sqrt2}\big)^n \big(|0 \rangle+(-1)^{x_1}|1 \rangle\big)...\big(|0 \rangle+(-1)^{x_n}|1 \rangle\big)$$
$$=\frac{1}{\sqrt{2^n}} \prod_i|0 \rangle+(-1)^{x_i}|1 \rangle$$
$$=\frac{1}{\sqrt{2^n}} \sum_{y \in\{0,1\}^n}f(y,x) |y \rangle$$
Now lets find $f(x,y)$. Notice that in the product line, if we expand we only get one term for each basis element in the Hilbert Space $H^n$, and each term in the expanded sum has either a coefficient of $+1$ or $-1$, based on the term itself and the $x$ which is undergoing the Hadamard Transform. Also notice that every $|0 \rangle$ has a $+1$ coefficient, so only the $|1 \rangle$ terms can contribute to negativity. So for each term with an odd number of $|1 \rangle$ that have a negative coefficient, the expanded term will also have a negative coefficient.
Finally notice that if $y_i=1$ then the term is a $|1 \rangle$ and if $x_i=1$ then the coefficient of that $|1 \rangle$ is negative. So iff $x_iy_i=1$ then we have a negative factor contributing to the $|y \rangle$, and of course if there is an odd number of those negative factors; the end result is a negative factor. This can be mathematically shown as:
$$=\frac{1}{\sqrt{2^n}} \sum_{y \in\{0,1\}^n} (-1)^{\sum_i^n x_iy_i} |y \rangle$$
$$=\frac{1}{\sqrt{2^n}} \sum_{y \in\{0,1\}^n} (-1)^{x \cdot y} |y \rangle$$
