This is a half of the solution... we exclude the case n is not a power of 3. Instead of working on the vertices of a n-gon, we work in $\mathbb{Z}_{n}$. The sequence is defined as: $a_{0}=0$ $a_{1}= 1$ $a_{n+2}= 2^{-1}a_{n+1}+2^{-1}a_{n}$ This is a standard recurrence... it characteristic equation is $x^{2}-2^{-1}x-2^{-1}$ with roots: $2^{-1}(2^{-1}\pm (2^{-2}+2^{2}\cdot 2^{-1})^{\frac{1}{2}}) = 2^{-2}\pm 2^{-1}(2^{-2}(1+8))^{\frac{1}{2}}= 2^{-2}\pm 3\cdot 2^{-2}$ ok, the roots are $1,-2^{-1}$. So, the solution is of the form $a_{n}= k(-2^{-1})^{n}+j$. First, we suppose $3 \nmid n$. Checking for n=0,1 we get $k=-2\cdot3^{-1}, j = 2 \cdot 3^{-1}$. Finally we get: $a_{n}=-2\cdot 3^{-1}\cdot(-2^{-1})^{n}+2\cdot 3^{-1}$. A function of $\mathbb{Z}_{n}$ is surjective iff $af(x)+b$, with $a \neq 0$ is surjective. Then we have only to check that $(-2)^{-n}$ is surjective, but this obviously false because it is never 0. Finally, the number of vertices we get is the order of -2 modulo n. (if n is not a multiple of 3). If n is a multiple of 3, we prove that the same sequence is not surjective in $\mathbb{Z}_{k}$, where k is the greatest divisor of n that is not a multiple of 3. To prove this, just use the method above. Since the sequence is not surjective in $\mathbb{Z}_{k}$, it is not also in $\mathbb{Z}_{n}=\mathbb{Z}_{k}\times \mathbb{Z}_{3^{i}}$. The case n is a power of 3 remains open... I have checked that with n=3,9 it is surjective.

Let $f$ be a function whose domain is $\left\{A_1,A_2,\cdots,A_k\right\}$ and such that $f(A_1)=0$, $f(A_2)=1$ and $f(A_k)$ is the arithmetic mean of $f(A_{k-1})$ and $f(A_{k-2})$, for $k\ge3$. Then it's easy to prove, using strong induction, that $f(A_{k+2})=\frac{2^{k+1}+(-1)^k}{3\cdot2^k}$, for $k\ge-1$. Suppose $n$ is a power of $3$. Let $p\ne3$ be a prime divisor of $n$. Let $m$ be an integer such that $3m\equiv_p2$ and suppose there is a vertex $A_{k+2}$ such that $f(A_{k+2})\equiv_nm$. Therefore we have: $f(A_{k+2})\equiv_pm\Leftrightarrow2^{k+1}+(-1)^k\equiv_p3m\cdot2^k\Leftrightarrow(-1)^k\equiv_p2^k(3m-2)\Leftrightarrow(-1)^k\equiv_p0$, which is impossible. Therefore $n$ must be a power of $3$. Lemma: $\mbox{ord}_{3^k}(-2)=3^{k-1}$, where $k$ is a positive integer. Proof: For $k=1$ it's trivial. Consider $k\ge2$. Since $3^1\parallel(-2)-1$ and $3^{k-1}\parallel3^{k-1}$, then, lifting the exponent, we have $3^k\parallel(-2)^{3^{k-1}}-1$, therefore $\mbox{ord}_{3^k}(-2)\mid3^{k-1}$. Suppose $\mbox{ord}_{3^k}(-2)\ne3^{k-1}$. Then $\mbox{ord}_{3^k}(-2)\mid3^{k-2}$, therefore $3^k\mid(-2)^{3^{k-2}}$. Since $(-2)^{3^{k-1}}-1=((-2)^{3^{k-2}}-1)((-2)^{2\cdot3^{k-2}}+(-2)^{3^{k-2}}+1)$, $3^k\mid(-2)^{3^{k-2}}-1$ and $3\mid(-2)^{2\cdot3^{k-2}}+(-2)^{3^{k-2}}+1$, then $3^{k+1}\mid(-2)^{3^{k-1}}-1$, a contradiction. Now let's prove that, for every integer $m$, there is a vertex $A_{k+2}$ such that $f(A_{k+2})\equiv_nm$. Therefore we have: $f(A_{k+2})\equiv_nm\Leftrightarrow2^{k+1}+(-1)^k\equiv_{3n}3m\cdot2^k\Leftrightarrow(-2)^k(3m-2)\equiv_{3n}1$. Note that $3m-2$ covers all the remainders modulo $3n$ that are congruent to $1$ modulo $3$. From the Lemma, $(-2)^k$ covers all the remainders modulo $3n$ that are congruent to $1$ modulo $3$, from where the result follows. Concluding, each vertex of the $n$-agon occurs on the sequence if and only if $n$ is a power of $3$.