# Prove: $\lfloor \rho^n + \frac{1}{2} \rfloor$ is divisible by $4$ iff $n$ is odd and divisible by $3$.

Let $\rho$ be the Golden Ratio $$\rho = \frac{1+\sqrt{5}}{2}$$ Prove that $\rho^n$, rounded to the nearest integer, is divisible by $4$ if and only if $n$ is odd and divisible by $3$.

That is, prove $\lfloor \rho^n + \frac{1}{2} \rfloor$ is divisible by $4$ if and only if $n$ is odd and divisible by $3$.

This is a fun problem, for those of us with just a tiny smattering of number theory. As a hint, $\rho$ is intimately connected to the Fibonacci sequence.

Real experts, please leave the fun to the others on this one because it is somewhat easy (though far from trivial).

• suggest Lucas instead, en.wikipedia.org/wiki/Lucas_number – Will Jagy Nov 10 '14 at 20:44
• The most pedantic of comments: I would say that $\rho^n$ rounded to the nearest integer is $\lceil \rho^n+\frac12 \rceil$. – Greg Martin Nov 10 '14 at 20:59
• @GregMartin, no, take 1.75, add 0.5, get 2.25, ceiling is 3 – Will Jagy Nov 10 '14 at 21:04
• aha, you're right, what I mean is $\lceil \rho^n - \frac12 \rceil$. I'm not trying to change anything except its values at half-integers. Which I know $\rho^n$ never equals anyway. – Greg Martin Nov 11 '14 at 3:13