Closed Form for an Alternating Sum Involving Binomial Coefficients 
Question. For integer $n \geq 0$, find the closed form for
  $$
S_n = \sum_{k \leq 2^n} \binom{2^n - k}{k}(-1)^k
$$

My Attempt: I tried some small $n$ and got $S_0 = 1$, $S_1 = 1$, $S_2 = 0$, $S_3 = -1$ and $S_4 = -1$, but failed to come up with some patterns. Could you please provide some hints so that I can complete the remaining part by myself?

The calculation is not correct in all aspects. We obtain
\begin{align*}
\color{blue}{S_0}&=\sum_{k=0}^1\binom{1-k}{k}(-1)^k=\binom{1}{0}=\color{blue}{1}\\
\color{blue}{S_1}&=\sum_{k=0}^2\binom{2-k}{k}(-1)^k=\binom{2}{0}-\binom{1}{1}
=1-1=\color{blue}{0}\\
\color{blue}{S_2}&=\sum_{k=0}^4\binom{4-k}{k}(-1)^k=\binom{4}{0}-\binom{3}{1}+\binom{2}{2}
=1-3+1=\color{blue}{-1}\\
\color{blue}{S_3}&=\sum_{k=0}^8\binom{8-k}{k}(-1)^k
=\binom{8}{0}-\binom{7}{1}+\binom{6}{2}-\binom{5}{3}+\binom{4}{4}\\
&=1-7+15-10+1=\color{blue}{0}\\
\color{blue}{S_4}&=\sum_{k=0}^{16}\binom{16-k}{k}(-1)^k\\
&=\binom{16}{0}-\binom{15}{1}+\binom{14}{2}-\binom{13}{3}+\binom{12}{4}-\binom{11}{5}\\
&\qquad+\binom{10}{6}-\binom{9}{7}+\binom{8}{8}\\
&=1-15+91-286+495-462+210-36+1=\color{blue}{-1}\\
\end{align*}

Hint: Since the index $2^n$ increases quickly it is not easy to manually derive the values of $S_n$. It looks plausible that we could more easily derive a pattern for
  \begin{align*}
T_m&=\sum_{k \leq m} \binom{m - k}{k}(-1)^k\qquad\qquad m\geq 0
\end{align*}
Observe that $S_n=T_{2^m}$ for $m\geq 0$. So, if we can observe a pattern for the sequence $T_m$
  we can derive from it a pattern for the sequence
  \begin{align*}
S_n=T_{2^m}
\end{align*}

