2
$\begingroup$

I have the formula:

$f(n) = \frac{p^n - q^n}{\sqrt 5}$

Assuming I know the value of $f(n)$, can I calculate $n$?

Sure, I can convert to $ \sqrt 5*f(n) = p^n - q^n$ . But after that I stuck...


edit 1

$p = \frac{1 + \sqrt 5}{2}$

$q = \frac{1 - \sqrt 5}{2}$

$\endgroup$
  • $\begingroup$ Is $n$ necessarily a natural number? And do you have $p$ and $q$? Are they integers? $\endgroup$ – Arthur Apr 1 '19 at 14:02
  • $\begingroup$ n is not necessary an integer. I have the values of p and q, yes. Addded in the description. $\endgroup$ – Predicate Apr 1 '19 at 14:03
  • $\begingroup$ $q$ is negative, so $q^n$ will be complex if $n$ is not an integer. In other words, when $f_n$ is real, there will be no solutions other than in those cases where $f_n$ is Fibonacci, and then the solutions are (uniquely) determined easily. $\endgroup$ – Andreas Apr 1 '19 at 14:43
  • $\begingroup$ You can't always do this. We have that $f(1)=f(2)=1$ so given $f(n)=1$ there is no formula which will give a definite result. For large $n$ we have that $q^n$ is very small and taking logarithms gives an accurate estimate (nearest integer) for $f(n)\ge 2$ where $f(n)$ is a fibonacci number. $\endgroup$ – Mark Bennet Apr 1 '19 at 16:16
2
$\begingroup$

I'll assume $n$ is an integer as otherwise I don't know how to interpret $q^n$. then $f(n)$ is also an integer, and because $|q|<1$ for large $n$ (in fact $n>1$) you have $$f(n)=\frac{p^n-q^n}{\sqrt{5}}=\left[\frac{p^n}{\sqrt{5}}\right],$$ where $[x]$ denotes the nearest integer to $x$. This shows that $$n\approx\log_p(\sqrt{5}f(n)).$$

$\endgroup$
  • $\begingroup$ It is a really good approximation, thank you. $\endgroup$ – Predicate Apr 1 '19 at 14:42
  • $\begingroup$ Can we assume, taking a rounded $n$ from your formula, that $fibonacci(n)$ would be equal to the n-th fibonacci? $\endgroup$ – Predicate Apr 1 '19 at 14:54
  • $\begingroup$ @Arthur edited to "rounded n" $\endgroup$ – Predicate Apr 1 '19 at 14:56
2
$\begingroup$

Assume $f(n)$ is real. Then there will be no solutions for the problem, other than in the case where $n$ is integer which entails that $f(n)$ is a Fibonacci number.

Proof:

Observe $q = \frac{1 - \sqrt 5}{2} <0$. So $q^n = \left(\frac{\sqrt 5-1}{2}\right)^n \cdot e^{i \pi n}$ where the first factor is a positive real. Now the imaginary part of $e^{i \pi n}$ vanishes only for integer $n$. This leads to two cases:

(1) let $n$ not be an integer. Then $p^n$ is real and $q^n$ has a nonvanishing imaginary part, so for real $f(n)$, there is no solution to $f(n) = \frac{p^n - q^n}{\sqrt 5}$.

(2) let $n$ be integer. Then $f(n) = \frac{p^n - q^n}{\sqrt 5}$ is exactly Binet's formula for Fibonacci numbers, which are the only cases where there is a solution for real $f(n)$. Since for $n>1$, the Fibonacci series $f(n)$ is strictly monotonously increasing, $n$ is uniquely determined. Servaes's answer gives a nice clue to find $n\approx\log_p(\sqrt{5}f(n))$.

$\endgroup$
1
$\begingroup$

As @Andreas has pointed out, the function $f(n) = (\varphi^n - (-\varphi)^{-n})/\sqrt 5$ is not real-valued unless $n$ is an integer. So typically one would be interested in replacing $f(n)$ with its real part, which is well-defined and entire:

$$ g(x) = \Re f(x) = \frac{\varphi^x - \cos(\pi x)\varphi^{-x}}{\sqrt 5} $$

See also the discussion at previous Question Non integer Fibonacci numbers and its earlier linked Question Interpolated Fibonacci numbers - real or complex?

In any case $g(x)$ is real-valued for $x$ real and monotone increasing for $x\ge 2$, so solutions to $g(x) = k$ can be uniquely determined for $x\in[2,+\infty)$ for all integers $k\ge 1$. Although $g(x)$ is a transcendental function, it is analytic in the complex plane; Newton iterations will converge rapidly given reasonable initial estimates for root $x$.

In particular since the OP commented on Servaes' Answer, "$f(n)$ is always integer in my problem," the initial estimate given there will be adequate for large $k\gg 1$:

$$ x \approx \log_\varphi (k \sqrt 5) $$

For modest positive integers $k$ it might be worthwhile to identify whether $k$ is Fibonacci, and if not, to bracket $k$ with its nearest lower/upper Fibonacci numbers to interpolate an initial guess.

$\endgroup$
0
$\begingroup$

I don't think there is a general way of solving this exactly. You might be in luck with your specific values of $p$ and $q$, but i doubt it. Unless $f(n)$ is a Fibonacci number, I'd just go with approximations, numerical methods or online calculators like WolframAlpha for each specific value of $f(n)$.

$\endgroup$
  • $\begingroup$ The connection with Fibonacci numbers is worth exploring in greater detail, as it seems possible that Binet's formula does lead to a more explicit solution when "$f(n)$ is a Fibonacci number". $\endgroup$ – hardmath Apr 1 '19 at 14:21
  • $\begingroup$ @hardmath If $f_n$ is Fibonacci, then by Binet we have exactly $f(n)=\frac{p^n-q^n}{\sqrt{5}}$, with the $p,q$ given by OP. Since for $n>1$, $f_n$ is strictly monotonously increasing, $n$ is uniquely determined and this is the solution (directly). $\endgroup$ – Andreas Apr 1 '19 at 14:39
  • $\begingroup$ @Andreas Most of that argument carries over for non-fibonacci $f(n)$ as well. It's just that if $f(n)$ happens to be fibonacci, then we know $n$ is an integer, and that makes the search for the solution much easier. But even for $f(n) = 43$, say, there is only one solution with $n>1$. It's a lot harder to find, but it's there. $\endgroup$ – Arthur Apr 1 '19 at 14:42
  • $\begingroup$ Well, for all real $f(n)$ which are not Fibonacci there are no solutions at all since if $n$ is not integer, $p^n$ is real and $q^n$ is complex, so the RHS is complex and this is a contradiction to real $f(n)$. $\endgroup$ – Andreas Apr 1 '19 at 14:46
  • $\begingroup$ @Andreas I missed that $q$ was negative. Cool. $\endgroup$ – Arthur Apr 1 '19 at 14:48

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.