Mathematical Induction on Matrix Sequence Given $M_0=(1)_{1\times1}$.
Denote:
$$ M_{i+1}=\begin{pmatrix}
M_i &-M_i \\ 
M_i & M_i 
\end{pmatrix} \; for\; i=0,1,2,...$$
Prove that $M_i$ is a square matrix of order $2^i \times2^i$ and all $M_i$ entries are $\pm 1$. Also prove $M^{T}_{i}M_i=2^i I_{2^i}$.

I do not know how to construct the matrix after from the assumption of mathematical induction. Thank you for noticing this question.
 A: We prove by induction on $i$ that for every $i \geq 0$, $M_i$ is a $2^i \times 2^i$ square matrix whose entries are all $\pm 1$, and that $M_i^T M_i = 2^i I_{2^i}$. I leave it to you to verify that this is true in the base case $i = 0$.
Assume the claim holds for some $i$, and consider $M_{i+1}$. By definition, $M_{i+1}$ is a $2 \times 2$ block matrix whose blocks are of size $2^i \times 2^i$, so of course $M_{i+1}$ is of size $2^{i+1} \times 2^{i+1}$. Its entries are either those of $M_i$ or $-M_i$; by the induction hypothesis, the entries of $M_i$ are $\pm 1$, and hence the same holds for $-M_i$, from which it follows that the entries of $M_{i+1}$ are $\pm 1$ also.
Next, convince yourself that
$$ M_{i+1}=\begin{pmatrix}
M_i &-M_i \\ 
M_i & M_i 
\end{pmatrix} \implies M_{i+1}^T=\begin{pmatrix}
M_i^T & M_i^T \\ 
-M_i^T & M_i^T 
\end{pmatrix} \; $$
Using this and the induction hypothesis, it follows that
\begin{align}
M_{i+1}^T M_{i+1} & = \begin{pmatrix}
M_i^T & M_i^T \\ 
-M_i^T & M_i^T 
\end{pmatrix} \begin{pmatrix}
M_i &-M_i \\ 
M_i & M_i 
\end{pmatrix} = \begin{pmatrix} 2 M_i^T M_i & 0 \\ 0 & 2 M_i^T M_i \end{pmatrix} \\
& = 2 \begin{pmatrix} 2^i I_{2^i} & 0 \\ 0 & 2^i I_{2^i} \end{pmatrix} = 2^{i+1} \begin{pmatrix} I_{2^i} & 0 \\ 0 & I_{2^i} \end{pmatrix} = 2^{i+1} I_{2^{i+1}}
\end{align}
The result follows by induction.
