2

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

Superluminal
  • 175
  • Is $n$ necessarily a natural number? And do you have $p$ and $q$? Are they integers? – Arthur Apr 01 '19 at 14:02
  • n is not necessary an integer. I have the values of p and q, yes. Addded in the description. – Superluminal Apr 01 '19 at 14:03
  • $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. – Andreas Apr 01 '19 at 14:43
  • 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. – Mark Bennet Apr 01 '19 at 16:16
  • Use this trinomial series solution to get the general inverse function – Тyma Gaidash Nov 30 '23 at 20:01

4 Answers4

2

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

Servaes
  • 63,261
  • 7
  • 75
  • 163
2

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

Andreas
  • 15,175
1

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.

hardmath
  • 37,015
0

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

Arthur
  • 199,419
  • 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". – hardmath Apr 01 '19 at 14:21
  • @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). – Andreas Apr 01 '19 at 14:39
  • @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. – Arthur Apr 01 '19 at 14:42
  • 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)$. – Andreas Apr 01 '19 at 14:46
  • @Andreas I missed that $q$ was negative. Cool. – Arthur Apr 01 '19 at 14:48
  • $f(n)$ is always integer in my problem. But its cool to follow your thought process guys – Superluminal Apr 01 '19 at 14:50
  • I'll put that into a full answer. – Andreas Apr 01 '19 at 15:16
  • Forgetting Fibonacci numbers, the problem of $p^x-q^x=k$ is very interesting from a numerical point of view if $1 < q < p$ and $k>0$. We could get an estimate very close to the solution. – Claude Leibovici Apr 01 '19 at 15:42