Prove that $3\sum\limits_{i=0}^k\binom{n}{3i}\leq2^n+2$ If $n\in \mathbb{Z^+}$ and $k$ is the largest integer for which $3k\leq n$, then is it true that $\sum_{i=0}^k\binom{n}{3i}\leq \frac{1}{3}(2^n+2)$?
My work: We can break this into two cases: $n=3k+1$ and $n=3k+2$.If $n=3k+1$, then we need to prove that $$\sum_{i=0}^k\binom{3k+1}{3k}\leq \frac{1}{3}(2^{3k+1}+2)$$ The first thing which strikes me is the fact that $2^{3k+1}=\sum_{i=0}^{3k+1}\binom{3k+1}{i}$ and the inequality can now be written after simplification as $$2\sum_{i=0}^k\binom{3k+1}{3i}\leq 2+\sum_{i=0}^k\binom{3k+1}{3i+1}+\sum_{i=0}^k\binom{3k+1}{3i+2}$$ but it does not seem to be helpful.Besides, there is another case($n=3k+2$) left to be tackled as well. Any ideas or hints will be useful. 
 A: 
Keyword: Discrete Fourier transform.

The third roots of unity $\zeta$ are such that $\sum\limits_\zeta\zeta^i=3$ if $i$ is a multiple of $3$ and $0$ otherwise. Hence,
$$
3\sum_i{n\choose3i}=\sum_i{n\choose i}\sum_\zeta\zeta^i=\sum_\zeta\sum_i{n\choose i}\zeta^i=\sum_\zeta(1+\zeta)^n.
$$
Now, $(1+\zeta)^n=2^n$ for $\zeta=1$ and it happens that $|1+\zeta|=1$ for both other roots of unity, hence
$$
\sum_\zeta(1+\zeta)^n=\left|\sum_\zeta(1+\zeta)^n\right|\leqslant\sum_\zeta|1+\zeta|^n=2^n+1+1,
$$
which ends the proof.
A: [This is essentially the same as Did's, but explicitly avoids the discrete Fourier Transform.]
We use the binomial theorem, which states that
$$ (x + 1 ) ^ n = \sum_{i=0}^n { n \choose i} x^ i $$
Since we want just those values where $i$ is a multiple of 3, we will use the fact that for $\omega \neq 1$ a cube root of 3, $\omega^2 + \omega + 1 = 0$, $ (\omega^2)^2 + \omega^2 + 1 = 0$, $ (\omega^3)^2 + \omega^3 + 1 = 3$.
Hence,
$\begin{array} {l l l l l l l l }
(1 + 1)^ n & = {n \choose 0} \times 1^0 & + {n \choose 1 } \times 1^1 & + {n\choose 2} \times 1^2 & + {n\choose 3} \times 1^3&  + \ldots &+ {n \choose n} \times 1^n\\
(\omega + 1)^n & =  {n \choose 0} \times \omega^0 & + {n \choose 1 } \times \omega^1 & + {n\choose 2} \times \omega^2 & + {n\choose 3} \times \omega^3 & + \ldots & + {n \choose n} \times \omega^n   \\
(\omega^2 + 1)^n & = {n \choose 0} \times (\omega^2) ^0 & + {n \choose 1 } \times (\omega^2) ^1 & + {n\choose 2} \times (\omega^2)^2 & + {n\choose 3} \times (\omega^2)^3 & + \ldots & + {n \choose n} \times (\omega^2)^n   \\
\hline\\
& {n \choose 0} \times 3 & + {n\choose 1 } \times 0 & + {n\choose 2} \times 0 & + {n\choose 3} \times 3 & + \ldots & + \ldots\\
\end{array}$
The last line is arrived at by adding up the previous 3 equations by the terms in the columns, and using the property of the cube root of unity. Hence, we see that 
$$ \sum_{i=0}^{\lfloor\frac{n}{3} \rfloor} { n \choose 3i} = \frac{ 2^n + (1+\omega)^n + (1+\omega^2)^n} { 3} = \frac{ 2^n + (-\omega)^{2n} + (-\omega)^n}{3} $$
Hence, we can arrive at your inequality since $|\omega| = 1$.
This can further be simplified to the form that Thomas mentioned.
A: Here’s a completely elementary solution. Let 
$$\begin{align*}
a_n&=\sum_k\binom{n}{3k}\;,\\
b_n&=\sum_k\binom{n}{3k+1}\;,\text{ and}\\
c_n&=\sum_k\binom{n}{3k+2}\;.
\end{align*}$$
Clearly $a_n+b_n+c_n=2^n$. Moreover, it follows from Pascal’s identity that
$$\begin{align*}
a_n&=a_{n-1}+c_{n-1}\;,\\
b_n&=b_{n-1}+a_{n-1}\;,\text{ and}\\
c_n&=c_{n-1}+b_{n-1}\;.
\end{align*}$$
Finally, $a_0=1$, and $b_0=c_0=0$, and the recurrences above make it very easy to calculate the first few values:
$$\begin{array}{c|ccc}
n&a_n&b_n&c_n\\ \hline
0&\color{red}1&0&0\\
1&1&1&\color{blue}0\\
2&1&\color{red}2&1\\
3&\color{blue}2&3&3\\
4&5&5&\color{red}6\\
5&11&\color{blue}{10}&11\\
6&\color{red}{22}&21&21
\end{array}$$
The pattern is clear: 
$$\begin{align*}
a_n&=\begin{cases}
\left\lceil\frac{2^n}3\right\rceil,&\text{if }n\equiv 0,1,5\pmod6\\\\
\left\lfloor\frac{2^n}3\right\rfloor,&\text{if }n\equiv 2,3,4\pmod6
\end{cases}\\\\
b_n&=\begin{cases}
\left\lceil\frac{2^n}3\right\rceil,&\text{if }n\equiv 1,2,3\pmod6\\\\
\left\lfloor\frac{2^n}3\right\rfloor,&\text{if }n\equiv 0,4,5\pmod6
\end{cases}\\\\
c_n&=\begin{cases}
\left\lceil\frac{2^n}3\right\rceil,&\text{if }n\equiv 3,4,5\pmod6\\\\
\left\lfloor\frac{2^n}3\right\rfloor,&\text{if }n\equiv 0,1,2\pmod6\;.
\end{cases}
\end{align*}\tag{1}$$
It’s a straightforward (if slightly tedious) matter to use the recurrences to prove $(1)$ by induction on $n$. Then merely note that for all $n$ we have
$$a_n\le\left\lceil\frac{2^n}3\right\rceil\le\frac{2^n+2}3\;.$$
