The problem is the following:
Fix $n\geq 1$ and let $\{S_{n,i}\}_{i\geq 1}$ be i.i.d. random variables whose common distribution is equal to $X_1+\dots + X_n$ for $X_i=\pm 1$ with probability $1/2$. Define $$M_n^{(c)}= \max_{1\leq I \leq e^{cn}} S_{n,i}$$ Then prove that for $c\in (0, \log 2)$, there exists constants $c_1,c_2,c_3,c_4$ (which only depend on $c$) such that $$ \lim_{n \to \infty} \mathbb{P}\left( \frac{M_n^{(c)}}{n}\leq c_1+c_2\frac{x+c_3}{n}+c_4\frac{\log(n)}{n}\right)=e^{-e^{-x}}$$
Determine the constants $c_1,c_2,c_3,c_4$ and show why the result fails when $c\geq \log2$.
Now I see that the right hand side is the Gumbel Distribution. And so I'd like to try to use the fact that if $X_i$ are i.i.d. and their CDF is $F(x)=1-e^{-x}$ (so they are exponentially distributed), and let $M_n=\max_{m\leq n}X_m$, then for any finite $y$, $\mathbb{P}(M_n-\log n \leq y) \rightarrow \exp(-e^{-y})$.
Or the following : if $X_1, X_2,\dots $ are i.i.d standard normal, define $b_n$ by $\mathbb{P}(X_i\geq b_n)=1/n$, and $M_n=\max (X_1,\dots, X_n)$, then $\mathbb{P}(b_n(M_n-b_n)\leq x) \rightarrow \exp(-e^{-x})$.
However, I do not really have any idea for this problem beyond the above facts about Gumbel Distribution. Any help is appreciated. Thank you.
You are correct in identifying that we are trying to obtain a Gumbel limit law, but the proof is a little more involved than the i.i.d. case. First, let $I$ be the large deviations rate function associated with $\{X_i\}$, i.e. \begin{align*} I(x):&=\sup_{\lambda\in\mathbb R}\Big(\lambda x-\log\mathbb E\left[e^{\lambda X_1}\right]\Big)\\ &=\begin{cases} x\tanh^{-1}(x)+\frac12\log(1-x^2)&\text{if }|x|<1,\\ +\infty&\text{otherwise.} \end{cases} \end{align*} Let $\rho=\rho_c$ be the unique $\rho\in(0,1)$ such that $I(\rho)=c$. (Observe that $I$ is strictly increasing on $(0,1)$ and $I(x)\to\log2$ as $x\uparrow1$, so this is possible if and only if $c\in(0,\log2)$.) The key estimate is from the Bahadur-Rao Theorem, which can be used to show there is some constant $C>0$ such that, provided $a_n=o(n^{1/2})$, $$\mathbb P\Big(S_{n,1}> n\rho-a_n\Big)\sim\frac{C}{\sqrt{n}}e^{-nI(\rho-a_n/n)}$$ as $n\to\infty$. Using the fact that $M_n^{(c)}\le y$ if and only if $S_{n,i}\le y$ for $1\le i\le e^{cn}$, we find $$\mathbb P\Big(M_n^{(c)}\le n\rho-a_n\Big)=\Big(1-\mathbb P\big(S_{n,1}> n\rho-a_n\big)\Big)^{e^{cn}}\sim\left(1-\frac{C}{\sqrt{n}}e^{-nI(\rho-a_n/n)}\right)^{e^{cn}}.$$ Setting $a_n=\frac1{2I'(\rho)}\log n-z$ and using the Taylor expansion of $I$ about $\rho$, we have $$I(\rho-a_n/n)=c-\frac12\frac{\log n}n+\frac{I'(\rho)z}n+O\left(\frac{\log^2n}{n^2}\right).$$ Hence $$\frac{1}{\sqrt{n}}e^{-nI(\rho-a_n/n)}=\frac{e^{-I'(\rho)z+O(\log^2n/n)}}{e^{cn}},$$ and so \begin{align*} \mathbb P\left(M_n^{(c)}\le n\rho-\frac1{2I'(\rho)}\log n+z\right)&\sim\left(1-\frac{Ce^{-I'(\rho)z+O(\log^2n/n)}}{e^{cn}}\right)^{e^{cn}}\\ &\to\exp\left(-Ce^{-I'(\rho)z}\right). \end{align*} To finish off, we just need to make a substitution to get rid of $C$ and $I'(\rho)$, and then identify the appropriate constants. To that end, let $x=\frac1{I'(\rho)}(z-\log C)$, and observe that we have shown $$\lim_{n\to\infty}\mathbb P\left(\frac{M_n^{(c)}}n\le\rho+I'(\rho)\frac{x+\log C/I'(\rho)}{n}-\frac1{2I'(\rho)}\frac{\log n}n\right)=e^{e^{-x}}$$ as required.
To show that we do not have such a limit for $c\ge\log2$, observe that $$\mathbb P(M_n^{(c)}<n)=\Big(1-\mathbb P(S_{n,1}=n)\Big)^{e^{cn}}=\Big(1-2^{-n}\Big)^{e^{cn}}\sim e^{-e^{(c-\log 2)n}},$$ so in particular $$\liminf_{n\to\infty}\mathbb P\Big(M_n^{(c)}=n\Big)\ge1-\frac1e.$$