<s>[INST] Prove that $\sum_{k=0}^{n}{n\choose 3k}\le\frac{1}{3}(2^n+2) \text{such that } n>0$ and $k$ is the largest number for which $3k\le n$ I tried it using induction
For $n=1,\displaystyle{1\choose 0}\le\dfrac{1}{3}(2^1+2)$
Let for $m\le n $ it is true i.e  $\displaystyle \sum_{k=0}^{n}{m\choose 3k}\le\dfrac{1}{3}(2^m+2)$
Now we need to prove for $m+1 \le n,\displaystyle \sum_{k=0}^{n}{m+1\choose 3k}\le\dfrac{1}{3}(2^{m+1}+2)$
Now $\displaystyle \sum_{k=0}^{n}{m+1\choose 3k}=\sum_{k=0}^{n}{m\choose 3k}+\sum_{k=1}^n {m\choose {3k-1}}$
Now the in the RHS, $\displaystyle \sum_{k=0}^{n}{m\choose 3k}+\sum_{k=1}^n {m\choose {3k-1}}\le \dfrac{1}{3}(2^m+2)+\underbrace{\sum_{k=1}^n {m\choose {3k-1}}}_{\text{Lets call this X}}=\dfrac{1}{3}(2^m+2)+X$
But how do I show $X \le \dfrac{1}{3}(2^m)$ in order to prove $\displaystyle \sum_{k=0}^{n}{m\choose 3k}+\sum_{k=1}^n {m\choose {3k-1}} \le \dfrac{1}{3}(2^{m+1}+2)$
 [/INST] It's not hard to notice that the left-hand side is equal to $\frac 13 \left((1+\zeta_3)^n + (1+\zeta_3^2)^n + (1+\zeta_3^3)^n\right)$, where $\zeta_3$ is the third root of unity. Now the inequality is equivalent to:
$$(1+\zeta_3)^n + (1+\zeta_3^2)^n \le 2$$
However now we have that $1+\zeta_3 = \zeta_6$ and $1+\zeta_3^2 = \zeta_6^5$ and we have that as the left-hand side is real:
$$ (1+\zeta_3)^n + (1+\zeta_3^2)^n = \left| (1+\zeta_3)^n + (1+\zeta_3^2)^n \right| = \left|\zeta_6^{5n} + \zeta_6^{n}\right| \le \left|\zeta_6^{5n}\right| + \left|\zeta_6^{n}\right| = \left|\zeta_6\right|^{5n} + \left|\zeta_6\right|^{n}=2$$
Hence the proof.
</s>