Sum involving golden ratio [Solution]

The problem was to find

$$S_n = \sum_{k=1}^{n} [k \varphi]$$

where $\varphi$ is the golden ratio and $[x]$ is the integer part of $x$.

The challenge was to do it using polynomial in $\log n$ time.

Solution

---

If you look at the numbers of the form $a_k = [k \varphi]$ and *not* of the form $[k \varphi]$, you will notice a pattern.

The pattern is as follows:

If $a_k = [k \varphi]$ and $b_k = a_k + k$, then we have that $$\{a_1, a_2, \dots\} \cup \{b_1, b_2, \dots\} = \mathbb{N}$$

i.e, the numbers not of the form $[k \varphi]$, are precisely of the form $[k \varphi] + k$.

This observation can be proved using Beatty's theorem (and is not that difficult to prove).

Now, if you consider the numbers $\{1, 2, \dots, a_n\}$ then these can be split into two disjoint sets $\{a_1, a_2, \dots, a_n\}$ and $\{b_1, b_2, \dots, b_m\}$ for some $m$.

Thus we have that

$$1 + 2 + \dots + a_n = S_n + \sum_{k=1}^{m} b_m = S_n + S_m + m(m+1)/2$$

Thus

$$S_n = n(n+1)/2 - m(m+1)/2 - S_m$$

which is a recursive formula for $S_n$. It can be shown that $m = \theta(n)$, and thus this recursive formula gives us a polynomial in $\log n$ time algorithm to compute $S_n$.

All we need to do is compute $m$. I will leave that to you.