# How to calculate $n$ in $f = p^n - q^n$?

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

• Is $n$ necessarily a natural number? And do you have $p$ and $q$? Are they integers? – Arthur Apr 1 '19 at 14:02
• n is not necessary an integer. I have the values of p and q, yes. Addded in the description. – Predicate Apr 1 '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 1 '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 1 '19 at 16:16

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

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

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

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.

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

• 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 1 '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 1 '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 1 '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 1 '19 at 14:46
• @Andreas I missed that $q$ was negative. Cool. – Arthur Apr 1 '19 at 14:48