9
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ Thats the golden ratio i think there exists some special series $\endgroup$ Feb 7 '16 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 '16 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 '16 at 14:34
  • $\begingroup$ @ZubinMukerjee The problem name is also "A Lucas Sum" in Brilliant.org $\endgroup$ Feb 7 '16 at 14:36
  • $\begingroup$ "$\lfloor \cdot \rceil$ denotes the nearest integer function." $\endgroup$ Feb 7 '16 at 14:45
4
$\begingroup$

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}$$

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

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$.

$\endgroup$
6
  • $\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 '16 at 14:41
  • $\begingroup$ @ZubinMukerjee: Thanks, in the middle of writing that bit up. $\endgroup$
    – Ron Gordon
    Feb 7 '16 at 14:44
  • $\begingroup$ What is about the denominator $2^k$? $\endgroup$ Feb 7 '16 at 14:48
  • $\begingroup$ @RezwanArefin: see the bit about the generating function. $\endgroup$
    – Ron Gordon
    Feb 7 '16 at 14:48
  • 1
    $\begingroup$ @ZubinMukerjee: keeping me honest! Forgot a word, hopefully that makes sense. $\endgroup$
    – Ron Gordon
    Feb 7 '16 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.