9
$\begingroup$

The Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones:

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34,.... $

So what if we sum converting these fibonacci series into decimal form according to their order, such as:

enter image description here

So What is the $Y$?

Note: $Y$ is an integer.

$\endgroup$
  • 1
    $\begingroup$ converting these fibonacci series into decimal form? I'm not following. $\endgroup$ – ibrahim mahrir Dec 1 '17 at 23:38
  • 1
    $\begingroup$ @ibrahimmahrir cant follow the example at least? $\endgroup$ – Oray Dec 1 '17 at 23:38
  • 1
    $\begingroup$ The "conversion to decimal form" appears to be `f(n)*10^-n? $\endgroup$ – Mooing Duck Dec 2 '17 at 17:00
8
$\begingroup$

Interestingly, I learnt about this in the past week, using something called a generating function (sort of like an infinite polynomial, but it's a bit more complicated than that).

So we start off by making a generating function, to do with the Fibonacci numbers:

$$g(x)=1+x+2x^2+3x^3+5x^4+8x^5+13x^6+\cdots$$

Note the following:

$$xg(x)=x+x^2+2x^3+3x^4+5x^5+8x^6+13x^7+\cdots$$ $$x^2g(x)=x^2+x^3+2x^4+3x^5+5x^6+8x^7+13x^8+\cdots$$

So by the definition of the Fibonacci numbers, $g(x)=1+xg(x)+x^2g(x)$.

But then $-g(x)+xg(x)+x^2g(x)=-1\implies g(x)=-\frac{1}{x^2+x-1}$.

So if it exists, the limit for $x=0.1$ is $g(0.1)=-\frac{1}{0.01+0.1-1}=-\frac{1}{-0.89}=\frac{100}{89}$.

Now, this is $10$ times what we want, since our initial terms of the generating sequence are $1$, $0.1$, $0.02$ etc., so we divide by $10$ again to get the correct answer, $\frac{10}{89}$ where $Y=89$.


The little issue of convergence:

Convergence isn't something we can show using generating functions. So first note that all the terms in the sum (except the initial $0$) are positive. Therefore the partial sums are strictly increasing.

Now:

$$\frac{1}{10^1}+\frac{1}{10^2}+\frac{1}{10^3}+3\cdot\frac{1}{10^4}+\cdots<\frac{1}{4^1}+\frac{1}{4^2}+2\cdot\frac{1}{4^3}+3\cdot\frac{1}{4^4}+\cdots$$

This is in turn less than:

$$2^1\cdot\frac{1}{4^1}+2^2\cdot\frac{1}{4^2}+2^3\cdot\frac{1}{4^3}+2^4\cdot\frac{1}{4^4}+2^5\cdot\frac{1}{4^5}+\cdots$$

This is clearly bigger than the previous number, since the leading two terms are both bigger and each term is the sum of $1.5$ times the previous two terms.

But this is equal to

$$\frac{1}{2^1}+\frac{1}{2^2}+\frac{1}{2^3}+\frac{1}{2^4}+\frac{1}{2^5}+\cdots=1$$

so the original summation is bounded above by $1$.

So by the monotone convergence theorem, the sum is convergent (the monotone convergence theorem basically says if a sequence keeps increasing but can't go past a certain number, it can't jiggle around too much after some particular number of items in the sequence).

$\endgroup$
8
$\begingroup$

In looking for $Y$, we can start by finding $S = \sum_{n=1}^{\infty} \frac{F_n}{10^n}.$

Expanding out the first two terms, we get:

$S = \frac{1}{10} + \frac{1}{100} + \sum_{n=3}^{\infty} \frac{F_n}{10^n}$

Expanding the summation, we get:

$S = \frac{11}{100} + \sum_{n=3}^{\infty} \frac{F_{n-1}+F_{n-2} }{10^n}$

Separating the summation, we get:

$S = \frac{11}{100} + \frac{1}{10} \sum_{n=3}^{\infty} \frac{ F_{n-1} }{10^{n-1} } + \frac{1}{100} \sum_{n=3}^{\infty} \frac{F_{n-2} }{10^{n-2} }$

Rewriting in terms, of S, note that:

$\frac{1}{10} \sum_{n=3}^{\infty} \frac{ F_{n-1} }{10^{n-1} } = \frac{1}{10} \left(S - \frac{1}{10} \right)$ and that $\frac{1}{100} \sum_{n=3}^{\infty} \frac{ F_{n-2} }{10^{n-2} } = \frac{1}{100} S$

So ultimately,

$S = \frac{11}{100} + \frac{1}{10} \left( S - \frac{1}{10} \right) + \frac{1}{100} S $

Solving for this, we get $S = \frac{10}{89}$ and so $Y = 89$.

$\endgroup$
6
$\begingroup$

This method is cheating, but ...

The question states that $Y$ is an integer.

The question also states that the sum (let's call it $S$) produces a continuation of the decimal number 0.1123595.

So $0.112 < S < 0.113$. But $Y = \frac{10}{S}$, so the only integer that fits is:

$$Y = 89$$

Proving the lower bound:

We have $f_1 = f_2 = 1$ and for $n \geq 2$, $$f_{n+2} = f_{n+1} + f_{n}$$

Consider the series starting $g_1 = g_2 = 1$ and for $n \geq 2$, $$g_{n+2} = 2g_{n}$$

Then by inspection, $f_n \leq g_n$.

The geometric sum $$G = \sum_i^\infty 10^{-i}g_i$$ sums to 0.1125, so the corresponding Fibonacci sum has $F < 0.1125$, resulting in $Y > 88.88$.

Proving the upper bound

Form the $g'$ series by adding an initial term '1' to the $g$ series to get (1,1,1,2,4,...) instead of (1,1,2,4,...).

Then we have $f_n \geq g_n$ by inspection, giving us $F > 0.11125$ and hence $Y < 89.89$.

The only integer between these bounds is $Y = 89$.

$\endgroup$
  • $\begingroup$ :) I knew this was coming lol... $\endgroup$ – Oray Dec 1 '17 at 23:26
  • 1
    $\begingroup$ @Oray Haha! I'm trying to make it a little more rigorous. No promises on that count, though. :) $\endgroup$ – Lawrence Dec 1 '17 at 23:30
  • $\begingroup$ @Oray Ok, now it just relies Y being an integer. Still a hack. :) $\endgroup$ – Lawrence Dec 2 '17 at 0:02
5
$\begingroup$

According to Wikipedia the Fibinacci numbers can be expressed as

$$F_n = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right)$$

So summing over your expoentially decreasing series

$$\sum\limits_{n=0}^{\infty} 10^{-n} F_n = \sum\limits_{n=0}^{\infty} 10^{-n} \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right) $$ $$ = \frac{1}{\sqrt{5}} \left( \left( \sum\limits_{n=0}^{\infty} \left( \frac{1 + \sqrt{5}}{20} \right)^n \right) - \left( \sum\limits_{n=0}^{\infty} \left( \frac{1 - \sqrt{5}}{20} \right)^n \right) \right) $$ and using the geometric sum gives $$ \frac{1}{\sqrt{5}} \left( \frac{1}{1 - \frac{1 + \sqrt{5}}{20}} - \frac{1}{1 - \frac{1 - \sqrt{5}}{20}} \right) = \frac{10}{89}$$. For the last step either do a lot of algebra or see for example Wolfram Alpha.

Edit: I see, too much Wikipedia spoils some puzzles:

Also on the Wikipedia page about the Fibonacci numbers, a bit further down there is a formula for $$ \sum\limits_{n=0}^{\infty} \frac{F_n}{k^n} = \frac{k}{k^2 - k - 1} \quad \text{for $k \in \mathbb{N}$.}$$ If we set $k = 10$, then the rest is easy.

$\endgroup$
  • $\begingroup$ Was about to post the same. Fibonacci numbers satisfy a Pisot recurrence, whence results of this sort are not at all surprising. $\endgroup$ – yo' Dec 2 '17 at 19:38

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.