Integer sequence comparison, binomials Vs power I need to know which sequence grows faster with n:
$$ f(n) = \sum_0^{floor(n/3)}  {n \choose 3*i+1} $$
compared to 
$$ g(n) = 2^n -1 $$
it seems f(10)>5000 is greater than g(10)=1023 but I would like to know what happen for greater n's
edit: is $f(n)$ equivalent $n^4$ so the g(n) should grow faster?
edit2: sorry I forgot $\sum_0^n  {n \choose i}  = 2^n$
 A: If $\zeta = e^{2 \pi i /3}$ is a primitive third root of unity then an explicit formula for $f(n)$ is
$$
f(n) = \sum_{k \equiv 1 \pmod{3}} {n \choose k} = \frac{1}{3} \left( (1 + 1)^n + \zeta^{-1} (1 + \zeta)^n + \zeta (1 + \zeta^{-1})^n \right).
$$
Now $1 + \zeta$ is a sixth root of unity and $1 + \zeta^{-1}$ is its conjugate (and inverse). So $f(n) = \tfrac{1}{3} 2^n + R(n)$ where $|R(n)| \leq \tfrac{2}{3}$.
A: (You might be interested in the 'offset modular generalization' in my answer here. Also see modular arithmetic and root of unity for preliminary material from Wikipedia. I will use $\lfloor\cdot\rfloor$ as the floor function and $a\equiv b(n)$ as shorthand for $a\equiv b\bmod n$.)
Let $\omega=\exp(2\pi i/3)$ be our choice of primitive third root of unity. We'll work with
$$f(n)=\sum_{k=0}^{\lfloor n/3\rfloor}\binom{n}{3k+1}=\sum_{m\equiv1(3)}\binom{n}{m}=\sum_m\binom{n}{m}[m\equiv1(3)].$$
Recall that if $m$ is an integer outside of the range $0\le\circ\le n$, the coefficient $\binom{n}{m}$ is zero, so the above sum makes sense. With the binomial theorem and the fact that $1+\omega+\omega^2=0$, we can rewrite the Iverson bracket $[m\equiv1(3)]$ algebraically as $(1+\omega^{m-1}+\omega^{2(m-1)})/3$ (this expression has period $3$ as a function of $m$, so to check this it suffices to check $m=0,1,2$; for motivation behind this see my linked answer). Hence
$$\begin{array}{c l} f(n) & =\sum_{m=0}^n \binom{n}{m}\frac{1+\omega^{m-1}+\omega^{2m-2}}{3} \\
& =\frac{1}{3}\sum_{m=0}^n \binom{n}{m}+\frac{\omega^{-1}}{3}\sum_{m=0}^n \binom{n}{m}\omega^m+\frac{\omega^{-2}}{3}\sum_{m=0}^n \binom{n}{m}\omega^{2m} \\
& = \frac{(1+1)^n+\omega^{-1}(1+\omega)^n+\omega^{-2}(1+\omega^2)^n}{3} \end{array}$$
As WimC notes, $\lambda=1+\omega$ is a sixth root of unity with conjugate $1+\omega^{-1}$ (remember $\omega^{-1}=\omega^2$ as well), so by triangle inequality
$$|3f(n)-2^n|\le |\omega^{-1}(1+\omega)^n|+|\omega^{-2}(1+\omega^2)^n|\le 1+1=2.$$
Hence the error between $f(n)$ and $2^n/3$ oscillates indefinitely, but will always be bounded in magnitude by $2/3$.
