combinatorial identity another solution? I would appreciate if somebody could help me with the following problem:
I need to show that,
$$\sum^{33}_{k=0}\binom{100}{3k}=\sum^{49}_{k=0}4^k$$
My proof is the following:
$$(1+x)^{100} = a_0 + a_1x + a_2x^2 + \cdots + a_{100}x^{100}$$
Let
$A = a_0 + a_3 + a_6 + \cdots + a_{99}, B = a_1 + a_2 + a_4 + a_5 + a_7 + a_8 + \cdots + a_{98} + a_{100}$$
then
$$A+B = 2^{100}$$
$$x^3=1 \to  x=1,w,w^2$$
$x$ put  $w$, $w^2$ and sum
$$\begin{align*}
(1+w)^{100} + (1+w^2 )^{100} 
&=w^{200} + w^{100}\\
&=w^{2} + w\\
&=-1\\
&= 2A + a_1(w+w^2) + a_2(w^2 + w^4) + a_4(w^4 + w^8) + \cdots + a_{100}(w^{100} + w^{200}) \\
&= 2A - B 
\end{align*}$$
therfore
$$A+B = 2^{100}, 2A - B=-1$$
$$A = \frac{2^{100} - 1}{3} = \frac{4^{50} - 1}{3} =\sum^{49}_{k=0}4^k $$
But I want to know if exists another proof for this problem.
 A: My argument uses more or less a discrete Fourier transform in a standard way to pick off every third coefficient. Let $\zeta_3 = \exp(2\pi i/3)$ be a primitive 3rd root of unity. Note that $1^k + \zeta_3^k + \zeta_3^{2k} = 3\delta_{3 \mid k}$. Letting $p(x) := (1+x)^{100}$, we see
$$\begin{align*}
\frac{p(1)+p(\zeta_3)+p(\zeta_3^2)}{3} = \frac{1}{3} \sum_{k=0}^{100} \binom{100}{k} (1^k + \zeta_3^k + \zeta_3^{2k}) = \sum_{k=0}^{33} \binom{100}{3k}.\end{align*}$$
On the other hand, $p(1)=2^{100}$ and $p(\zeta_3) = (1+\zeta_3)^{100}$. As is well-known, $1, \zeta_3, \zeta_3^2$ form the vertices of an equilateral triangle, and $1+\zeta_3, -1, 1+\zeta_3^2$ form the remaining vertices of a regular hexagon. Anyway, $1+\zeta_3$ has a polar angle of $\pi/3$. Hence $(1+\zeta_3)^{100}$ has a polar angle of $100\pi/3 \equiv 4\pi/3$ and a magnitude of $1$. Likewise $(1+\zeta_3^2)^{100}$ has a polar angle of $-4\pi/3$ and a magnitude of $1$. Hence $p(\zeta_3) + p(\zeta_3^2) = 2\cos(4\pi/3) = -1$. So, the left-hand side is
$$\begin{align*}\frac{2^{100} - 1}{3}
&= \frac{4^{50} - 1}{4 - 1} = \sum_{i=0}^{49} 4^i\end{align*}$$
(Note: I wrote this while your argument was unreadable. They seem to be similar in spirit.)
A: $\newcommand{\bbx}[1]{\,\bbox[15px,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}$
My answer is somehow similar to the one by
$\ds{\tt @Joshua\ P.\ Swanson}$. However, there are some differences.
\begin{align}
&\bbox[5px,#ffd]{\sum_{k = 0}^{33}{100 \choose 3k}} =
\sum_{k = 0}^{99}{100 \choose k}{1 + \expo{2k\pi\ic/3} + \expo{-2k\pi\ic/3} \over 3}
\\[5mm] = &\
{1 \over 3}\sum_{k = 0}^{99}{100 \choose k} +
{2 \over 3}\,\Re\sum_{k = 0}^{99}{100 \choose k}
\pars{\expo{2\pi\ic/3}}^{k}
\\[5mm] = &\
{1 \over 3}\pars{2^{100} - 1} +
{2 \over 3}\,\Re\bracks{\pars{1 + \expo{2\pi\ic/3}}^{100} -
\expo{200\pi\ic/3}}
\\[5mm] = &\
{2^{100} \over 3} +
{2 \over 3}\,\Re\bracks{\pars{{1 \over 2} +
{\root{3} \over 2}\,\ic}^{100}}
\\[5mm] = &\
{2^{100} \over 3} +
{2 \over 3}\,\Re\bracks{\pars{\expo{\ic\pi/3}}^{100}} =
{2^{100} \over 3} +
{2 \over 3}\cos\pars{100\pi \over 3}
\\[5mm] = &\
{2^{100} \over 3} - {1 \over 3} =
{4^{50} - 1 \over 4 - 1} = \bbx{\sum_{k = 0}^{49}4^{k}} \\ &
\end{align}
