Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
What is $E$? If it's less than $1$, explicit formulas seem out of the picture. –  anon May 30 '12 at 16:06
it's round(x)-1 –  kwak May 30 '12 at 16:10
How do you get $f(10)>5000$ when $f(n)$ is certainly less than the sum of all the coefficients on the $n$-th, which is $2^n$ ?? –  Ragib Zaman May 30 '12 at 16:23
yes wrong calcul –  kwak May 30 '12 at 16:34

2 Answers 2

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}$.

share|improve this answer

(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$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.