# Let $a=\dfrac{3+\sqrt{5}}{2}.$ Show that $\lfloor a \lfloor an \rfloor \rfloor+n$ is divisible by $3$.

Let $a=\dfrac{3+\sqrt{5}}{2}.$

Show that for all $n\in\mathbb N$, $\lfloor a \lfloor an \rfloor \rfloor+n$ is divisible by $3$.

My teacher solve this problem with induction, I am just curious if we can do this exercise without it ?

-
Where did you get that nice question from? –  Samurai May 10 '14 at 20:24
@Samurai It was in my teacher exercise paper. –  Edwin May 11 '14 at 9:38

It is in fact the case that, for $a = \frac{3 + \sqrt{5}}{2}$, $$\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \boldsymbol{\floor{a \floor{ a n}} + n = 3 \floor{a n}.}$$ Proof. Let $r = a n - \floor{a n}$, $0 < r < 1$. Then $\floor{a n} = (a n - r)$, so we need to show that \begin{align*} 3(a n - r) - n &\le a (a n - r) < 3(a n - r) - n + 1 \\ 3 a n - 3 r - n &\le a^2 n - r < 3 a n - 3 r - n + 1 \\ \end{align*} Notice that $a$ satisfies $a^2 = 3 a - 1$. This reduces the above to $$3 a n - 3 r - n \le 3 a n - a r - n < 3 a n - 3 r - n + 1$$ Adding $3r + n - 3a n$, $$0 \le (3 - a) r < 1$$ which is true since $0 < r < 1$ and $$3 - a = \frac{3 - \sqrt{5}}{2} < \frac{3 - 2}{2} < 1.$$

-

Let $\alpha=\dfrac{1+\sqrt{5}}{2}, \beta=\dfrac{3+\sqrt{5}}{2}$, then

$$\beta= \alpha^2= \alpha+1$$

Since $$\alpha\lfloor\beta n\rfloor-\lfloor\beta n\rfloor=\alpha n-(\alpha-1)\{\alpha n\}=\lfloor\alpha n\rfloor+(2-\alpha)\{\alpha n\}$$

so $\lfloor\alpha n\rfloor\lt \alpha\lfloor\beta n\rfloor-\lfloor\beta n\rfloor\lt \lfloor\alpha n\rfloor+1$. we get that

$$\lfloor\alpha\lfloor\beta n\rfloor\rfloor=\lfloor\alpha n\rfloor+\lfloor\beta n\rfloor$$

then, we have

$$\begin{split}\lfloor\beta\lfloor\beta n\rfloor\rfloor+n &=\lfloor\alpha\lfloor\beta n\rfloor+\lfloor\beta n\rfloor \rfloor+n\\&=\lfloor\alpha\lfloor\beta n\rfloor\rfloor+\lfloor\beta n\rfloor +n\\ &=\lfloor\alpha n\rfloor+\lfloor\beta n\rfloor+\lfloor\beta n\rfloor +n\\ &=\lfloor\alpha n\rfloor+2\lfloor\beta n\rfloor +n\\ &=\lfloor\alpha n\rfloor+2\lfloor\alpha n +n\rfloor +n\\ &=3\lfloor\alpha n\rfloor +3n \end{split}$$

-
At the end, $3 \lfloor \alpha n \rfloor + 3n$ has the simpler form $3 \lfloor \beta n \rfloor$. In light of this fact, and because I think the part of the proof you left out is the only hard / interesting part of the proof, I've added my own answer below. –  Goos May 10 '14 at 19:03
@Goos Thanks! I add some detail... –  Clin May 10 '14 at 19:16
(@Goos) Thank you both. –  Edwin May 10 '14 at 19:49