<s>[INST] 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. 
 [/INST] 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\;.$$
</s>