Let $p = \sqrt{1+\sqrt{1+\sqrt{1 + \cdots}}}$
The sum $$\sum_{k=2}^{\infty}{\dfrac{\lfloor p^k \rceil}{2^k}}$$
Can be expressed as $\frac{a}{b}$. Where $\lfloor \cdot \rceil$ denotes the nearest integer function. Find $a+b$.

My Work
$p^2 = 1+p \implies p = \dfrac{1+\sqrt{5}}{2} = \phi$
And also $\phi^n = \dfrac{L_n + F_n\sqrt{5}}{2}$. Where $L_n$ is the $n-th$ Lucas-Number.
What to do with the next part?

Note: Problem Collected from Brilliant.org

  • 1
    $\begingroup$ Thats the golden ratio i think there exists some special series $\endgroup$ Feb 7, 2016 at 14:29
  • 1
    $\begingroup$ Would it help? Observe that $p^2=1+p$, $p^3=p(p^2)=p(1+p)=1+2p$,$p^4=\ldots=2+3p$, one may write $p^n=F_{n-1}+F_n p$ $\endgroup$ Feb 7, 2016 at 14:31
  • 1
    $\begingroup$ Searching the first few terms in the OEIS gave me this. It appears that the sequence of nearest integers to $p^k$ is the same as the Lucas numbers (at least after the third term). $\endgroup$ Feb 7, 2016 at 14:34
  • $\begingroup$ @ZubinMukerjee The problem name is also "A Lucas Sum" in Brilliant.org $\endgroup$ Feb 7, 2016 at 14:36
  • $\begingroup$ "$\lfloor \cdot \rceil$ denotes the nearest integer function." $\endgroup$ Feb 7, 2016 at 14:45

2 Answers 2


You are correct that $$p=\frac{1+\sqrt{5}}{2}$$

This is the golden ratio, ususally labeled $\phi$. There is a well-known relationship between $\phi$ and the Lucas numbers $L_k$: for all natural numbers $k$,

$$L_k = \phi^k + \left(\frac{-1}{\phi}\right)^k$$

The second term above will be less than $1/2$ for $k >1$, so rounding $\phi^k$ to the nearest integer must give $L_k$.

This means your sum can be written in terms of Lucas numbers. Let your sum be $S$. Then

$$S = \displaystyle\sum\limits_{k=2}^{\infty} \frac{L_k}{2^k}$$

Now we can write out a few terms of $S$, $2S$, and $4S$:

\begin{align} S = \frac{L_2}{4}&+\frac{L_3}{8}+\frac{L_4}{16}+\frac{L_5}{32}+\cdots \\\\ 2S = \frac{L_2}{2}+\frac{L_3}{4}&+\frac{L_4}{8}+\frac{L_5}{16}+\cdots \\\\ 4S = L_2+\frac{L_3}{2}+\frac{L_4}{4}&+\frac{L_5}{8}+\frac{L_6}{16}\cdots \\ \end{align}

I've intentionally lined up the sums above like that because if we add up the first two equations, term by term, we get

$$ 3S = \frac{L_2}{2} + \frac{L_2+L_3}{4} + \frac{L_3+L_4}{8}+\frac{L_4 + L_5}{16}+\cdots $$

But the Lucas numbers, like the Fibonacci numbers, satisfy the recursion $L_k + L_{k+1} = L_{k+2}$. Therefore

$$3S = \frac{L_2}{2} + \left(\frac{L_4}{4} + \frac{L_5}{8} + \frac{L_6}{16}+\cdots\right)$$

But everything after the first term looks a lot like what we had written for $4S$ above! In fact, we can write

$$3S = \frac{L_2}{2} + \left(4S - L_2 - \frac{L_3}{2}\right)$$

$$S = \frac{L_2}{2} + \frac{L_3}{2}$$

$$S = \frac{L_4}{2}$$

Finally, we can solve for your sum:

$$S = \frac{7}{2}$$

  • 2
    $\begingroup$ Nice job, @Zubin. $\endgroup$
    – Ron Gordon
    Feb 7, 2016 at 15:26

For $n \ge 2$, the numbers $\lfloor \phi^k \rceil$ are equal to the Lucas numbers, which satisfy the Fibonacci recurrence but in which $L_1=1$ and $L_2=3$. The Lucas numbers satisfy

$$L_k = \phi^k + (-1)^k \phi^{-k}$$

and thus have the generating function

$$L(x) = \frac{2-x}{1-x-x^2} $$

so the sum we want is

$$L \left (\frac12 \right ) - L_0 - \frac12 L_1 = \frac72$$

Note that $\phi^{-1}= \phi-1 = 0.618\ldots$ and exponentiation to the power of $k$ does not affect a rounding for $k \ge 2$.

  • $\begingroup$ As for why they are equal to the Lucas numbers, this identity gives a good explanation: $$L_n = \phi^n + \left(\frac{-1}{\phi}\right)^n$$ The second term has absolute value less than $1/2$ for $n \geq 2$, and so it does not affect the rounding to the nearest integer. $\endgroup$ Feb 7, 2016 at 14:41
  • $\begingroup$ @ZubinMukerjee: Thanks, in the middle of writing that bit up. $\endgroup$
    – Ron Gordon
    Feb 7, 2016 at 14:44
  • $\begingroup$ What is about the denominator $2^k$? $\endgroup$ Feb 7, 2016 at 14:48
  • $\begingroup$ @RezwanArefin: see the bit about the generating function. $\endgroup$
    – Ron Gordon
    Feb 7, 2016 at 14:48
  • 1
    $\begingroup$ @ZubinMukerjee: keeping me honest! Forgot a word, hopefully that makes sense. $\endgroup$
    – Ron Gordon
    Feb 7, 2016 at 14:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .