0

Im trying to make a function that finds the length of a fibonacci sequence based upon its sum

I know $\sum f_n = f_{n+2} + f_2$

I know $f_n = \cfrac{\varphi^n-({-\varphi})^n}{\sqrt 5}$

so, $\sum f_n = \cfrac{\varphi^{n+2}-({-\varphi})^{-(n+2)}}{\sqrt 5}+1$

but, I need to rearrange it to isolate $n$

or, more generally, solve for $x$ in $z = p^x - ({-p})^{-x}$

also would this be computationally sound compared to generating the fib sequence until its total exceeds the target sum?

ie

def findTerm(sum):
    lastlast = 1
    last = 0
    n = 0

while 0 <= lamb:
    next = last + lastlast
    lastlast = last
    last = next

    sum -= next
    n += 1

return n - 1
Mr Pie
  • 9,459
Mason Hawver
  • 3

1 Answers1

0

I shall admit that we only use $F_n$ for $n >0$.

As you wrote, we have $$S_n=\sum_{i=1}^n F_i=F_{n+2}-1=\frac{\varphi ^{n+2}-\psi ^{n+2}}{\sqrt{5}}-1$$ and you want to find $n$ such that $$\varphi ^{n+2}-\psi ^{n+2}=\sqrt{5} (S_n+1)$$ If $S_n$ is large, $n$ will be large and $\psi ^{n+2}$ becomes negligible. Ignoring it and taking logarithms, a quick approximation is then given by $$(n+2)\log(\varphi) \sim \log\big[\sqrt{5} (S_n+1) \big]$$ that is to say $$n \sim \text{Round}\left[\frac{\log \left(\sqrt{5} (S_n+1)\right)}{\log (\varphi )}-2\right]$$

Trying with $S_n=9227465$, this would give before rounding $33.000000225$ so $n=33$ which is the exact answer. This works perfect as soon as $n >4$

Claude Leibovici
  • 260,315