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?
 A: Instead of computing a single sum, sometimes it will be easier if one


*

*generalize the sum into a series of related ones,

*combine them into a single generating function and solves for it,

*extract the sum from the coefficients of the generating function.


For this particular problem, we will adopt the convention that $\binom{\ell}{k} = 0$ whenever $\ell < k$.
We will look at generalization of the form
$$T_m = \sum_{k=0}^m \binom{m-k}{k}(-1)^k = \sum_{k=0}^\infty \binom{m-k}{k}(-1)^k$$
It is not that hard to work out the generating function for $T_m$:
$$\begin{align}
\sum_{m=0}^\infty T_m s^m 
&= \sum_{m=0}^\infty\sum_{k=0}^\infty \binom{m-k}{k} s^k (-1)^k
= \sum_{\ell=0}^\infty\sum_{k=0}^\infty \binom{\ell}{k}s^\ell (-s)^k\\
&= \sum_{\ell=0}^\infty s^\ell(1-s)^\ell = \frac{1}{1-s+s^2}
= \frac{1+s}{1+s^3} = \frac{1 + s - s^3 - s^4}{1 - s^6}
\end{align}
$$
If one compare coefficients of $t^m$ on both sides, we get
$$T_m = \sum_{k=0}^\infty \binom{m-k}{k}(-1)^k = \begin{cases}
+1,& k \equiv 0, 1 \pmod 6\\
-1,& k \equiv 3,4 \pmod 6\\
0, & \text{ otherwise }
\end{cases}
$$
Together with $$2^n \equiv \begin{cases}
1,& n = 0,\\
2,& n > 0, n \text{ odd}\\
4,& n > 0, n \text{ even}
\end{cases}$$
We can read off the value of the original sum as 
$$S_n = T_{2^n} = \sum_{k=0}^\infty \binom{2^n-k}{k}(-1)^k = 
\begin{cases}
1,& n = 0,\\
0,& n > 0, n \text{ odd}\\
-1,& n > 0, n \text{ even}
\end{cases}$$
A: Think about
$$T_m=\sum_k(-1)^k\binom{m-k}{k}$$
instead. Using the identity $\binom rs=\binom{r-1}{s-1}+\binom{r-1}s$
should give you a recurrence for $T_m$.
A: 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*}

A: $\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{S_{n} \equiv \sum_{k \leq 2^{n}}{2^n - k \choose k}\pars{-1}^{k}:\
{\large ?}}$.

$$
\mbox{Note that}\quad \bbx{\ds{S_{0} = {1 - 0 \choose 0}\pars{-1}^{0} +
{1 - 1 \choose 1}\pars{-1}^{1} = 1}}
$$

\begin{align}
\left.S_{n}\right\vert_{\ n\ \geq\ 1} & \equiv \sum_{k \leq 2^{n}}{2^n - k \choose k}\pars{-1}^{k} =
\sum_{k = 0}^{2^{n}}\pars{-1}^{k}\bracks{z^{k}}\pars{1 + z}^{2^{n} - k} =
\sum_{k = 0}^{2^{n}}\pars{-1}^{k}\bracks{z^{0}}\bracks{{1 \over z^{k}}
{\pars{1 + z}^{2^{n}} \over \pars{1 + z}^{k}}}
\\[5mm] & =
\bracks{z^{0}}\pars{1 + z}^{2^{n}}\sum_{k = 0}^{2^{n}}
\bracks{-\,{1 \over z\pars{1 + z}}}^{k} =
\bracks{z^{0}}\pars{1 + z}^{2^{n}}\,
{\braces{-1/\bracks{z\pars{1 + z}}}^{2^{n} + 1} - 1 \over \braces{-1/\bracks{z\pars{1 + z}}} - 1 }
\\[5mm] & =
\bracks{z^{0}}\pars{1 + z}^{2^{n}}\braces{%
{1 \over \bracks{z\pars{1 + z}}^{2^{n}}}\,
{1 + \bracks{z\pars{z + 1}}^{\,2^{n} + 1} \over z^{2} + z + 1}} =
\bracks{z^{2^{n}}}
{1 + \bracks{z\pars{z + 1}}^{\,2^{n} + 1} \over z^{2} + z + 1} 
\\[5mm] & =
\bracks{z^{2^{n}}}{1  \over z^{2} + z + 1} =
\bracks{z^{2^{n}}}{1 - z \over 1 - z^{3}} =
\bracks{z^{2^{n}}}\bracks{%
\sum_{k = 0}^{\infty}z^{3k} - \sum_{k = 0}^{\infty}z^{3k + 1}} =
-\bracks{z^{2^{n}}}\sum_{k = 0}^{\infty}z^{3k + 1}
\end{align}

$$\bbox[15px,#ffe,border:1px dotted navy]{\ds{%
\left.S_{n}\right\vert_{\ n\ \geq\ 0} \equiv
\sum_{k \leq 2^{n}}{2^n - k \choose k}\pars{-1}^{k} =
\left\{\begin{array}{rl}
\ds{1} & \mbox{if}\ \ds{n = 0}
\\[1mm]
\ds{-1} & \mbox{if}\quad
\ds{\exists\ k \in \mathbb{N}_{\ \geq\ 0}\quad \mid\quad 3k + 1 = 2^{n}\,,\quad
n \geq 1}
\\[1mm]
\ds{0} & \mbox{otherwise}
\end{array}\right.}}
$$
Note that


If $\ds{n}$ is even,
  $\ds{{2^{n} - 1 \over 3} = {4^{n/2} - 1 \over 3} =
1 + 4 + 4^{2} + \cdots + 4^{n/2 - 1}}$
If $\ds{n}$ is odd,
  $\ds{{2^{n} - 1 \over 3} = {2\bracks{4^{\pars{n - 1}/2} - 1} + 1 \over 3} =
2\bracks{1 + 4 + 4^{2} + \cdots + 4^{\pars{n - 3}/2}} + {1 \over 3}}$


$$\bbox[15px,#ffe,border:1px dotted navy]{\ds{%
\left.S_{n}\right\vert_{\ n\ \geq\ 0} \equiv
\sum_{k \leq 2^{n}}{2^n - k \choose k}\pars{-1}^{k} =
\left\{\begin{array}{rl}
\ds{1} & \mbox{if}\ \ds{n = 0}
\\[1mm]
\ds{-1} & \mbox{if}\quad n \geq 2\ \mbox{is}\ even
\\[1mm]
\ds{0} & \mbox{if}\quad n \geq 1\ \mbox{is}\ odd
\end{array}\right.}}
$$
