1
$\begingroup$

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$

  • 0
    yes wrong calcul2012-05-30

2 Answers 2

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

0

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