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. 

[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.
