If the Fibonacci sequence is defined such that $F_1=F_2=1$, compute $$\sum_{j=1}^{2012}i^{2012-F_j}$$ where $i$ is the imaginary unit.
I tried writing out the terms and using the laws of exponents and I got $$\frac{i^{2012}}{i^{F_1}}+\frac{i^{2012}}{i^{F_2}}+\frac{i^{2012}}{i^{F_3}}+\cdots+\frac{i^{2012}}{i^{F_{2012}}}$$ which reduces to $$\frac{1}{i^{F_1}}+\frac{1}{i^{F_2}}+\frac{1}{i^{F_3}}+\cdots+\frac{1}{i^{F_{2012}}}$$
I don't know how to further manipulate this with the cyclic nature of powers of $i$. Any help would be appreciated. Thanks!
What helps here, is that you are taking $i$ to the power something. Since $i^4 = 1$ it is enough to understand what is the remainder of the power when divided by $4$, rather than the power itself.
That is, we are reduced to finding the remainder of $2012-F_j$ upon division by $4$, rather than the number itself. Since $2012$ is divisible by $4$, we are essentially looking at the remainder when $-F_j$ is divided by $4$.
For starters, $F_i$ goes like : $-1,-1,-2,-3,-5,-8,-13,-21,-34,-55,-89,-144,...$, and the remainders go like : $3,3,2,1,3,0,3,3,2,1,3,0,...$. Is the pattern clear? Well, $3,3,2,1,3,0$ seems to be repeating.
To see why this must be true, one must use the recurrence $F_{n+2} = F_{n+1} + F_n$, but one can ignore multiples of four, since we are only looking at remainders upon division by four.
EDIT : I will actually use congruence notation here. $\equiv$ means having the same remainder when divided by $4$.
$$ F_{n+3} \equiv F_{n+2} + F_{n+1} \equiv F_n + 2F_{n+1} \\ F_{n+4} \equiv F_{n+3} + F_{n+2} \equiv 2F_n + 3F_{n+1} \\ F_{n+5} \equiv F_{n+4} + F_{n+3} \equiv 3F_n + 5F_{n+1} = 3F_n + F_{n+1} \\ {\color{blue}{F_{n+6} \equiv F_{n+5} + F_{n+4} \equiv 5F_n + 4F_{n+1} = F_n}} $$
Hence, $F_{n+6}$ and $F_n$ always leave the same remainder when divided by $4$ (and this doesn't happen for any number smaller than $6$). Therefore, since this is true for all $n$, we know that there is some cycle of period $6$, which is precisely the cycle of remainders of Fibonacci numbers modulo four. That is $3,3,2,1,3,0$.
Now, to use this, break $j = 1 \to 2012$ into blocks of $6$ consecutive numbers, and the rest. The block is easy to evaluate since: $$ i^3 + i^3 + i^2 + i^1 + i^3 + i^0 = -3i +-1 + 1 + i = -2i $$
Now, note that $335 \times 6 = 2010$, so the sequence of remainders is like: $$ \underbrace{3,3,2,1,3,0,....,3,3,2,1,3,0}_{335\text { times}} ,3,3 $$
and hence the sum required is $335 \times (-2i) + i^3 +i^3 = -672i$.