How can I find an inverse to the Binet formula?
$begingroup$
I'm already aware of the Binet formula $displaystyle F_n = frac{varphi^n + frac{1}{varphi^n}}{sqrt{5}}$. I'm attempting to find the inverse of that formula so I can find the position in the sequence of Fibonacci numbers. In fact, at first glance it's relatively easy:
$$
F_nsqrt{5} = varphi^n + frac{1}{varphi^n}\
varphi^nF_nsqrt{5} = varphi^{2n} + 1\
varphi^{2n} - varphi^nF_nsqrt{5}+ 1 = 0\
varphi^n = frac{F_nsqrt{5}+ sqrt{5F_n^2 - 4}}{2}\
n = log_varphileft(frac{F_nsqrt{5}+ sqrt{5F_n^2 - 4}}{2}right)
$$
But this isn't quite correct. The problem is that we must subtract or add 4 depending on whether the Fibonacci number has odd or even position in the sequence (or rather, whether $5F_n^2 - 4$ is a perfect square; admittedly, we could just go by this indicator, but I want to avoid that if at all possible). So the formula is actually:
$$
n = log_varphileft(frac{F_nsqrt{5}+ sqrt{5F_n^2 + 4(-1)^n}}{2}right)
$$
But that doesn't work for me, because n appears in multiple places in the formula, and you'd need to know if it's odd or even to be able to derive it. So if you do the work, you'll see that I'm trying to isolate n in the expression:
$$
varphi^{2n} - varphi^nF_nsqrt{5} = (-1)^n
$$
Or alternatively, find an operation that when applied to the numbers 3, 8, 21, 55, 144, etc. gives an even number, and when applied to the numbers 2, 5, 13, 34, 89 gives an odd number.
As a side note, I find it highly unnerving that the almighty quadratic formula fails in this particular case.
Update: I am only interested in solving either of the two problems posed above, not in other ways to find Fibonacci numbers' positions in the sequence.
fibonacci-numbers golden-ratio
edited Jan 10 at 1:10
El borito
664216
asked Apr 28 '13 at 0:33
LinusLinus
265
$endgroup$
|
show 1 more comment
$begingroup$
I'm already aware of the Binet formula $displaystyle F_n = frac{varphi^n + frac{1}{varphi^n}}{sqrt{5}}$. I'm attempting to find the inverse of that formula so I can find the position in the sequence of Fibonacci numbers. In fact, at first glance it's relatively easy:
$$
F_nsqrt{5} = varphi^n + frac{1}{varphi^n}\
varphi^nF_nsqrt{5} = varphi^{2n} + 1\
varphi^{2n} - varphi^nF_nsqrt{5}+ 1 = 0\
varphi^n = frac{F_nsqrt{5}+ sqrt{5F_n^2 - 4}}{2}\
n = log_varphileft(frac{F_nsqrt{5}+ sqrt{5F_n^2 - 4}}{2}right)
$$
But this isn't quite correct. The problem is that we must subtract or add 4 depending on whether the Fibonacci number has odd or even position in the sequence (or rather, whether $5F_n^2 - 4$ is a perfect square; admittedly, we could just go by this indicator, but I want to avoid that if at all possible). So the formula is actually:
$$
n = log_varphileft(frac{F_nsqrt{5}+ sqrt{5F_n^2 + 4(-1)^n}}{2}right)
$$
But that doesn't work for me, because n appears in multiple places in the formula, and you'd need to know if it's odd or even to be able to derive it. So if you do the work, you'll see that I'm trying to isolate n in the expression:
$$
varphi^{2n} - varphi^nF_nsqrt{5} = (-1)^n
$$
Or alternatively, find an operation that when applied to the numbers 3, 8, 21, 55, 144, etc. gives an even number, and when applied to the numbers 2, 5, 13, 34, 89 gives an odd number.
As a side note, I find it highly unnerving that the almighty quadratic formula fails in this particular case.
Update: I am only interested in solving either of the two problems posed above, not in other ways to find Fibonacci numbers' positions in the sequence.
fibonacci-numbers golden-ratio
edited Jan 10 at 1:10
El borito
664216
asked Apr 28 '13 at 0:33
LinusLinus
265
$endgroup$
$begingroup$
please update your title and the text of your question. As written it suggests that you are seeking an inverse to the Binet formula.
$endgroup$
– vadim123
Apr 28 '13 at 1:35
$begingroup$
Closely related: math.stackexchange.com/questions/191920/fibonacci-nth-term
$endgroup$
– Erick Wong
Apr 28 '13 at 2:17
$begingroup$
None of those answers gives an exact inverse. And I do believe one is possible, because the Binet formula isn't perfect; if you put in 0 you get $frac{2sqrt{5}}{5}$.
$endgroup$
– Linus
Apr 28 '13 at 5:19
$begingroup$
And if you put in 2 you get $frac{75 + 282sqrt{5}}{620}$, not quite the same thing as 1.
$endgroup$
– Linus
Apr 28 '13 at 5:32
1
$begingroup$
@Linus: Or, you could have the wrong formula.
$endgroup$
– Hurkyl
Apr 28 '13 at 9:10
|
show 1 more comment
$begingroup$
I'm already aware of the Binet formula $displaystyle F_n = frac{varphi^n + frac{1}{varphi^n}}{sqrt{5}}$. I'm attempting to find the inverse of that formula so I can find the position in the sequence of Fibonacci numbers. In fact, at first glance it's relatively easy:
$$
F_nsqrt{5} = varphi^n + frac{1}{varphi^n}\
varphi^nF_nsqrt{5} = varphi^{2n} + 1\
varphi^{2n} - varphi^nF_nsqrt{5}+ 1 = 0\
varphi^n = frac{F_nsqrt{5}+ sqrt{5F_n^2 - 4}}{2}\
n = log_varphileft(frac{F_nsqrt{5}+ sqrt{5F_n^2 - 4}}{2}right)
$$
But this isn't quite correct. The problem is that we must subtract or add 4 depending on whether the Fibonacci number has odd or even position in the sequence (or rather, whether $5F_n^2 - 4$ is a perfect square; admittedly, we could just go by this indicator, but I want to avoid that if at all possible). So the formula is actually:
$$
n = log_varphileft(frac{F_nsqrt{5}+ sqrt{5F_n^2 + 4(-1)^n}}{2}right)
$$
But that doesn't work for me, because n appears in multiple places in the formula, and you'd need to know if it's odd or even to be able to derive it. So if you do the work, you'll see that I'm trying to isolate n in the expression:
$$
varphi^{2n} - varphi^nF_nsqrt{5} = (-1)^n
$$
Or alternatively, find an operation that when applied to the numbers 3, 8, 21, 55, 144, etc. gives an even number, and when applied to the numbers 2, 5, 13, 34, 89 gives an odd number.
As a side note, I find it highly unnerving that the almighty quadratic formula fails in this particular case.
Update: I am only interested in solving either of the two problems posed above, not in other ways to find Fibonacci numbers' positions in the sequence.
fibonacci-numbers golden-ratio
edited Jan 10 at 1:10
El borito
664216
asked Apr 28 '13 at 0:33
LinusLinus
265
$endgroup$
I'm already aware of the Binet formula $displaystyle F_n = frac{varphi^n + frac{1}{varphi^n}}{sqrt{5}}$. I'm attempting to find the inverse of that formula so I can find the position in the sequence of Fibonacci numbers. In fact, at first glance it's relatively easy:
$$
F_nsqrt{5} = varphi^n + frac{1}{varphi^n}\
varphi^nF_nsqrt{5} = varphi^{2n} + 1\
varphi^{2n} - varphi^nF_nsqrt{5}+ 1 = 0\
varphi^n = frac{F_nsqrt{5}+ sqrt{5F_n^2 - 4}}{2}\
n = log_varphileft(frac{F_nsqrt{5}+ sqrt{5F_n^2 - 4}}{2}right)
$$
But this isn't quite correct. The problem is that we must subtract or add 4 depending on whether the Fibonacci number has odd or even position in the sequence (or rather, whether $5F_n^2 - 4$ is a perfect square; admittedly, we could just go by this indicator, but I want to avoid that if at all possible). So the formula is actually:
$$
n = log_varphileft(frac{F_nsqrt{5}+ sqrt{5F_n^2 + 4(-1)^n}}{2}right)
$$
But that doesn't work for me, because n appears in multiple places in the formula, and you'd need to know if it's odd or even to be able to derive it. So if you do the work, you'll see that I'm trying to isolate n in the expression:
$$
varphi^{2n} - varphi^nF_nsqrt{5} = (-1)^n
$$
Or alternatively, find an operation that when applied to the numbers 3, 8, 21, 55, 144, etc. gives an even number, and when applied to the numbers 2, 5, 13, 34, 89 gives an odd number.
As a side note, I find it highly unnerving that the almighty quadratic formula fails in this particular case.
Update: I am only interested in solving either of the two problems posed above, not in other ways to find Fibonacci numbers' positions in the sequence.
fibonacci-numbers golden-ratio
fibonacci-numbers golden-ratio
edited Jan 10 at 1:10
El borito
664216
asked Apr 28 '13 at 0:33
LinusLinus
265
edited Jan 10 at 1:10
El borito
664216
asked Apr 28 '13 at 0:33
LinusLinus
265
edited Jan 10 at 1:10
El borito
664216
edited Jan 10 at 1:10
El borito
664216
edited Jan 10 at 1:10
El borito
664216
664216
asked Apr 28 '13 at 0:33
LinusLinus
265
asked Apr 28 '13 at 0:33
LinusLinus
265
asked Apr 28 '13 at 0:33
LinusLinus
265
265
$begingroup$
please update your title and the text of your question. As written it suggests that you are seeking an inverse to the Binet formula.
$endgroup$
– vadim123
Apr 28 '13 at 1:35
$begingroup$
Closely related: math.stackexchange.com/questions/191920/fibonacci-nth-term
$endgroup$
– Erick Wong
Apr 28 '13 at 2:17
$begingroup$
None of those answers gives an exact inverse. And I do believe one is possible, because the Binet formula isn't perfect; if you put in 0 you get $frac{2sqrt{5}}{5}$.
$endgroup$
– Linus
Apr 28 '13 at 5:19
$begingroup$
And if you put in 2 you get $frac{75 + 282sqrt{5}}{620}$, not quite the same thing as 1.
$endgroup$
– Linus
Apr 28 '13 at 5:32
1
$begingroup$
@Linus: Or, you could have the wrong formula.
$endgroup$
– Hurkyl
Apr 28 '13 at 9:10
|
show 1 more comment
$begingroup$
please update your title and the text of your question. As written it suggests that you are seeking an inverse to the Binet formula.
$endgroup$
– vadim123
Apr 28 '13 at 1:35
$begingroup$
Closely related: math.stackexchange.com/questions/191920/fibonacci-nth-term
$endgroup$
– Erick Wong
Apr 28 '13 at 2:17
$begingroup$
None of those answers gives an exact inverse. And I do believe one is possible, because the Binet formula isn't perfect; if you put in 0 you get $frac{2sqrt{5}}{5}$.
$endgroup$
– Linus
Apr 28 '13 at 5:19
$begingroup$
And if you put in 2 you get $frac{75 + 282sqrt{5}}{620}$, not quite the same thing as 1.
$endgroup$
– Linus
Apr 28 '13 at 5:32
1
$begingroup$
@Linus: Or, you could have the wrong formula.
$endgroup$
– Hurkyl
Apr 28 '13 at 9:10
$begingroup$
please update your title and the text of your question. As written it suggests that you are seeking an inverse to the Binet formula.
$endgroup$
– vadim123
Apr 28 '13 at 1:35
$begingroup$
please update your title and the text of your question. As written it suggests that you are seeking an inverse to the Binet formula.
$endgroup$
– vadim123
Apr 28 '13 at 1:35
$begingroup$
Closely related: math.stackexchange.com/questions/191920/fibonacci-nth-term
$endgroup$
– Erick Wong
Apr 28 '13 at 2:17
$begingroup$
Closely related: math.stackexchange.com/questions/191920/fibonacci-nth-term
$endgroup$
– Erick Wong
Apr 28 '13 at 2:17
$begingroup$
None of those answers gives an exact inverse. And I do believe one is possible, because the Binet formula isn't perfect; if you put in 0 you get $frac{2sqrt{5}}{5}$.
$endgroup$
– Linus
Apr 28 '13 at 5:19
$begingroup$
None of those answers gives an exact inverse. And I do believe one is possible, because the Binet formula isn't perfect; if you put in 0 you get $frac{2sqrt{5}}{5}$.
$endgroup$
– Linus
Apr 28 '13 at 5:19
$begingroup$
And if you put in 2 you get $frac{75 + 282sqrt{5}}{620}$, not quite the same thing as 1.
$endgroup$
– Linus
Apr 28 '13 at 5:32
$begingroup$
And if you put in 2 you get $frac{75 + 282sqrt{5}}{620}$, not quite the same thing as 1.
$endgroup$
– Linus
Apr 28 '13 at 5:32
1
1
$begingroup$
@Linus: Or, you could have the wrong formula.
$endgroup$
– Hurkyl
Apr 28 '13 at 9:10
$begingroup$
@Linus: Or, you could have the wrong formula.
$endgroup$
– Hurkyl
Apr 28 '13 at 9:10
|
show 1 more comment
2 Answers
2
active
oldest
votes
$begingroup$
I think your formula is not Binet's. Binet's formula is
$$F_n=frac{varphi^n-frac{1}{(-varphi)^n}}{sqrt{5}},$$
which agrees with your formula for odd $n,$ but not for even $n$. In fact, for even $n$ the numbers your formula gives are not even rational.
So the quadratic formula does not fail. It's just that you've applied it to the wrong formula. Unfortunately the quadratic formula cannot be applied to the correct formula since the correct formula does not contain $varphi^n$ in both terms—one term contains $(-varphi)^n$ instead—and so your algebra doesn't go through the same way.
Another remark: the formula you are hoping to find must fail for $n=1$ or $2$ since $F_1=F_2=1$ and you can't have two different numbers as the inverse of $1.$
answered Apr 28 '13 at 22:40
Will OrrickWill Orrick
13.7k13461
$endgroup$
$begingroup$
Thank you. This is exactly the answer I wanted: why it can't be done, or how to derive it if it can be done. Actually, in theory one could apply the quadratic formula to the correct formula, but that would require knowledge of whether n is odd or even (i.e. $x^2(-x)^2 = x^4$ but $x^3(-x)^3 = -x^6$, and I asked this question to avoid knowing that
$endgroup$
– Linus
Apr 29 '13 at 0:16
$begingroup$
Now, is there such an operation as the one I describe, and/or is it possible to solve the final equation I give?
$endgroup$
– Linus
Apr 29 '13 at 3:05
$begingroup$
Can you explain what it is about operations that involve rounding that you find objectionable? I believe that any solution to your problem will either involve rounding, or will sneak rounding in through the back door. The answer is going to be an integer, so it should perhaps not be surprising that discrete operations come into play.
$endgroup$
– Will Orrick
Apr 29 '13 at 6:16
$begingroup$
You could, for example, square both sides of your equation. This gets rid of $(-1)^n,$ but the quadratic becomes a quartic. The four solutions to this quartic include the two solutions to the quadratic with right hand side $-1$ and the two solutions with right hand side $1.$ The rounding question is now replaced with the question of which root to take. We obtain $n$ by taking whichever of $log_varphifrac{sqrt{5}F+sqrt{5F^2+4}}{2}$ and $log_varphifrac{sqrt{5}F+sqrt{5F^2-4}}{2}$ is an integer. The ambiguity for $F=1$ manifests itself in that only in this case are both integers.
$endgroup$
– Will Orrick
Apr 29 '13 at 6:29
add a comment |
$begingroup$
The second term vanishes quite quickly. We have $F_n=lfloor frac{phi^n}{sqrt{5}}+frac{1}{2}rfloor$, where $lfloor cdot rfloor$ denotes the floor function. If the floor weren't there, you could solve for $n$, and if you rounded you would be wrong only for possibly very small $n$.
Update: A quick calculation shows that $n=left[ log_phi sqrt{5}(F_n-frac{1}{2}) right]$ holds for all $nge 3$, and fails for $n=1,2$. In this case $[cdot]$ denotes the rounding function, or $[x]=lfloor x+frac{1}{2}rfloor$.
answered Apr 28 '13 at 0:36
vadim123vadim123
76.5k897191
$endgroup$
$begingroup$
This isn't what I'm looking for. I want something exact.
$endgroup$
– Linus
Apr 28 '13 at 0:45
$begingroup$
What do you mean by exact? The expression above yields an integer that is the desired integer for all $n$ except $n=1,2$. You can take it $pmod{2}$ to answer your even/odd question as well.
$endgroup$
– vadim123
Apr 28 '13 at 0:49
$begingroup$
By exact, I mean that I want a general formula that doesn't fail at all. Even setting aside the failure, if you put 3 into that second expression you get 3.5764. Even taking into account that 4 should be added and not subtracted in my almost-correct initial formula, the result is 3.9075. If you add 4 the result is exactly 4.
$endgroup$
– Linus
Apr 28 '13 at 1:32
1
$begingroup$
See en.wikipedia.org/wiki/…
$endgroup$
– lhf
Apr 28 '13 at 1:58
2
$begingroup$
@Linus: vadim123’s formula gives the exact value for all $nge 3$.
$endgroup$
– Brian M. Scott
Apr 28 '13 at 9:29
|
show 1 more comment
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f374758%2fhow-can-i-find-an-inverse-to-the-binet-formula%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I think your formula is not Binet's. Binet's formula is
$$F_n=frac{varphi^n-frac{1}{(-varphi)^n}}{sqrt{5}},$$
which agrees with your formula for odd $n,$ but not for even $n$. In fact, for even $n$ the numbers your formula gives are not even rational.
So the quadratic formula does not fail. It's just that you've applied it to the wrong formula. Unfortunately the quadratic formula cannot be applied to the correct formula since the correct formula does not contain $varphi^n$ in both terms—one term contains $(-varphi)^n$ instead—and so your algebra doesn't go through the same way.
Another remark: the formula you are hoping to find must fail for $n=1$ or $2$ since $F_1=F_2=1$ and you can't have two different numbers as the inverse of $1.$
answered Apr 28 '13 at 22:40
Will OrrickWill Orrick
13.7k13461
$endgroup$
$begingroup$
Thank you. This is exactly the answer I wanted: why it can't be done, or how to derive it if it can be done. Actually, in theory one could apply the quadratic formula to the correct formula, but that would require knowledge of whether n is odd or even (i.e. $x^2(-x)^2 = x^4$ but $x^3(-x)^3 = -x^6$, and I asked this question to avoid knowing that
$endgroup$
– Linus
Apr 29 '13 at 0:16
$begingroup$
Now, is there such an operation as the one I describe, and/or is it possible to solve the final equation I give?
$endgroup$
– Linus
Apr 29 '13 at 3:05
$begingroup$
Can you explain what it is about operations that involve rounding that you find objectionable? I believe that any solution to your problem will either involve rounding, or will sneak rounding in through the back door. The answer is going to be an integer, so it should perhaps not be surprising that discrete operations come into play.
$endgroup$
– Will Orrick
Apr 29 '13 at 6:16
$begingroup$
You could, for example, square both sides of your equation. This gets rid of $(-1)^n,$ but the quadratic becomes a quartic. The four solutions to this quartic include the two solutions to the quadratic with right hand side $-1$ and the two solutions with right hand side $1.$ The rounding question is now replaced with the question of which root to take. We obtain $n$ by taking whichever of $log_varphifrac{sqrt{5}F+sqrt{5F^2+4}}{2}$ and $log_varphifrac{sqrt{5}F+sqrt{5F^2-4}}{2}$ is an integer. The ambiguity for $F=1$ manifests itself in that only in this case are both integers.
$endgroup$
– Will Orrick
Apr 29 '13 at 6:29
add a comment |
$begingroup$
I think your formula is not Binet's. Binet's formula is
$$F_n=frac{varphi^n-frac{1}{(-varphi)^n}}{sqrt{5}},$$
which agrees with your formula for odd $n,$ but not for even $n$. In fact, for even $n$ the numbers your formula gives are not even rational.
So the quadratic formula does not fail. It's just that you've applied it to the wrong formula. Unfortunately the quadratic formula cannot be applied to the correct formula since the correct formula does not contain $varphi^n$ in both terms—one term contains $(-varphi)^n$ instead—and so your algebra doesn't go through the same way.
Another remark: the formula you are hoping to find must fail for $n=1$ or $2$ since $F_1=F_2=1$ and you can't have two different numbers as the inverse of $1.$
answered Apr 28 '13 at 22:40
Will OrrickWill Orrick
13.7k13461
$endgroup$
$begingroup$
Thank you. This is exactly the answer I wanted: why it can't be done, or how to derive it if it can be done. Actually, in theory one could apply the quadratic formula to the correct formula, but that would require knowledge of whether n is odd or even (i.e. $x^2(-x)^2 = x^4$ but $x^3(-x)^3 = -x^6$, and I asked this question to avoid knowing that
$endgroup$
– Linus
Apr 29 '13 at 0:16
$begingroup$
Now, is there such an operation as the one I describe, and/or is it possible to solve the final equation I give?
$endgroup$
– Linus
Apr 29 '13 at 3:05
$begingroup$
Can you explain what it is about operations that involve rounding that you find objectionable? I believe that any solution to your problem will either involve rounding, or will sneak rounding in through the back door. The answer is going to be an integer, so it should perhaps not be surprising that discrete operations come into play.
$endgroup$
– Will Orrick
Apr 29 '13 at 6:16
$begingroup$
You could, for example, square both sides of your equation. This gets rid of $(-1)^n,$ but the quadratic becomes a quartic. The four solutions to this quartic include the two solutions to the quadratic with right hand side $-1$ and the two solutions with right hand side $1.$ The rounding question is now replaced with the question of which root to take. We obtain $n$ by taking whichever of $log_varphifrac{sqrt{5}F+sqrt{5F^2+4}}{2}$ and $log_varphifrac{sqrt{5}F+sqrt{5F^2-4}}{2}$ is an integer. The ambiguity for $F=1$ manifests itself in that only in this case are both integers.
$endgroup$
– Will Orrick
Apr 29 '13 at 6:29
add a comment |
$begingroup$
I think your formula is not Binet's. Binet's formula is
$$F_n=frac{varphi^n-frac{1}{(-varphi)^n}}{sqrt{5}},$$
which agrees with your formula for odd $n,$ but not for even $n$. In fact, for even $n$ the numbers your formula gives are not even rational.
So the quadratic formula does not fail. It's just that you've applied it to the wrong formula. Unfortunately the quadratic formula cannot be applied to the correct formula since the correct formula does not contain $varphi^n$ in both terms—one term contains $(-varphi)^n$ instead—and so your algebra doesn't go through the same way.
Another remark: the formula you are hoping to find must fail for $n=1$ or $2$ since $F_1=F_2=1$ and you can't have two different numbers as the inverse of $1.$
answered Apr 28 '13 at 22:40
Will OrrickWill Orrick
13.7k13461
$endgroup$
I think your formula is not Binet's. Binet's formula is
$$F_n=frac{varphi^n-frac{1}{(-varphi)^n}}{sqrt{5}},$$
which agrees with your formula for odd $n,$ but not for even $n$. In fact, for even $n$ the numbers your formula gives are not even rational.
So the quadratic formula does not fail. It's just that you've applied it to the wrong formula. Unfortunately the quadratic formula cannot be applied to the correct formula since the correct formula does not contain $varphi^n$ in both terms—one term contains $(-varphi)^n$ instead—and so your algebra doesn't go through the same way.
Another remark: the formula you are hoping to find must fail for $n=1$ or $2$ since $F_1=F_2=1$ and you can't have two different numbers as the inverse of $1.$
answered Apr 28 '13 at 22:40
Will OrrickWill Orrick
13.7k13461
answered Apr 28 '13 at 22:40
Will OrrickWill Orrick
13.7k13461
answered Apr 28 '13 at 22:40
Will OrrickWill Orrick
13.7k13461
answered Apr 28 '13 at 22:40
Will OrrickWill Orrick
13.7k13461
13.7k13461
$begingroup$
Thank you. This is exactly the answer I wanted: why it can't be done, or how to derive it if it can be done. Actually, in theory one could apply the quadratic formula to the correct formula, but that would require knowledge of whether n is odd or even (i.e. $x^2(-x)^2 = x^4$ but $x^3(-x)^3 = -x^6$, and I asked this question to avoid knowing that
$endgroup$
– Linus
Apr 29 '13 at 0:16
$begingroup$
Now, is there such an operation as the one I describe, and/or is it possible to solve the final equation I give?
$endgroup$
– Linus
Apr 29 '13 at 3:05
$begingroup$
Can you explain what it is about operations that involve rounding that you find objectionable? I believe that any solution to your problem will either involve rounding, or will sneak rounding in through the back door. The answer is going to be an integer, so it should perhaps not be surprising that discrete operations come into play.
$endgroup$
– Will Orrick
Apr 29 '13 at 6:16
$begingroup$
You could, for example, square both sides of your equation. This gets rid of $(-1)^n,$ but the quadratic becomes a quartic. The four solutions to this quartic include the two solutions to the quadratic with right hand side $-1$ and the two solutions with right hand side $1.$ The rounding question is now replaced with the question of which root to take. We obtain $n$ by taking whichever of $log_varphifrac{sqrt{5}F+sqrt{5F^2+4}}{2}$ and $log_varphifrac{sqrt{5}F+sqrt{5F^2-4}}{2}$ is an integer. The ambiguity for $F=1$ manifests itself in that only in this case are both integers.
$endgroup$
– Will Orrick
Apr 29 '13 at 6:29
add a comment |
$begingroup$
Thank you. This is exactly the answer I wanted: why it can't be done, or how to derive it if it can be done. Actually, in theory one could apply the quadratic formula to the correct formula, but that would require knowledge of whether n is odd or even (i.e. $x^2(-x)^2 = x^4$ but $x^3(-x)^3 = -x^6$, and I asked this question to avoid knowing that
$endgroup$
– Linus
Apr 29 '13 at 0:16
$begingroup$
Now, is there such an operation as the one I describe, and/or is it possible to solve the final equation I give?
$endgroup$
– Linus
Apr 29 '13 at 3:05
$begingroup$
Can you explain what it is about operations that involve rounding that you find objectionable? I believe that any solution to your problem will either involve rounding, or will sneak rounding in through the back door. The answer is going to be an integer, so it should perhaps not be surprising that discrete operations come into play.
$endgroup$
– Will Orrick
Apr 29 '13 at 6:16
$begingroup$
You could, for example, square both sides of your equation. This gets rid of $(-1)^n,$ but the quadratic becomes a quartic. The four solutions to this quartic include the two solutions to the quadratic with right hand side $-1$ and the two solutions with right hand side $1.$ The rounding question is now replaced with the question of which root to take. We obtain $n$ by taking whichever of $log_varphifrac{sqrt{5}F+sqrt{5F^2+4}}{2}$ and $log_varphifrac{sqrt{5}F+sqrt{5F^2-4}}{2}$ is an integer. The ambiguity for $F=1$ manifests itself in that only in this case are both integers.
$endgroup$
– Will Orrick
Apr 29 '13 at 6:29
$begingroup$
Thank you. This is exactly the answer I wanted: why it can't be done, or how to derive it if it can be done. Actually, in theory one could apply the quadratic formula to the correct formula, but that would require knowledge of whether n is odd or even (i.e. $x^2(-x)^2 = x^4$ but $x^3(-x)^3 = -x^6$, and I asked this question to avoid knowing that
$endgroup$
– Linus
Apr 29 '13 at 0:16
$begingroup$
Thank you. This is exactly the answer I wanted: why it can't be done, or how to derive it if it can be done. Actually, in theory one could apply the quadratic formula to the correct formula, but that would require knowledge of whether n is odd or even (i.e. $x^2(-x)^2 = x^4$ but $x^3(-x)^3 = -x^6$, and I asked this question to avoid knowing that
$endgroup$
– Linus
Apr 29 '13 at 0:16
$begingroup$
Now, is there such an operation as the one I describe, and/or is it possible to solve the final equation I give?
$endgroup$
– Linus
Apr 29 '13 at 3:05
$begingroup$
Now, is there such an operation as the one I describe, and/or is it possible to solve the final equation I give?
$endgroup$
– Linus
Apr 29 '13 at 3:05
$begingroup$
Can you explain what it is about operations that involve rounding that you find objectionable? I believe that any solution to your problem will either involve rounding, or will sneak rounding in through the back door. The answer is going to be an integer, so it should perhaps not be surprising that discrete operations come into play.
$endgroup$
– Will Orrick
Apr 29 '13 at 6:16
$begingroup$
Can you explain what it is about operations that involve rounding that you find objectionable? I believe that any solution to your problem will either involve rounding, or will sneak rounding in through the back door. The answer is going to be an integer, so it should perhaps not be surprising that discrete operations come into play.
$endgroup$
– Will Orrick
Apr 29 '13 at 6:16
$begingroup$
You could, for example, square both sides of your equation. This gets rid of $(-1)^n,$ but the quadratic becomes a quartic. The four solutions to this quartic include the two solutions to the quadratic with right hand side $-1$ and the two solutions with right hand side $1.$ The rounding question is now replaced with the question of which root to take. We obtain $n$ by taking whichever of $log_varphifrac{sqrt{5}F+sqrt{5F^2+4}}{2}$ and $log_varphifrac{sqrt{5}F+sqrt{5F^2-4}}{2}$ is an integer. The ambiguity for $F=1$ manifests itself in that only in this case are both integers.
$endgroup$
– Will Orrick
Apr 29 '13 at 6:29
$begingroup$
You could, for example, square both sides of your equation. This gets rid of $(-1)^n,$ but the quadratic becomes a quartic. The four solutions to this quartic include the two solutions to the quadratic with right hand side $-1$ and the two solutions with right hand side $1.$ The rounding question is now replaced with the question of which root to take. We obtain $n$ by taking whichever of $log_varphifrac{sqrt{5}F+sqrt{5F^2+4}}{2}$ and $log_varphifrac{sqrt{5}F+sqrt{5F^2-4}}{2}$ is an integer. The ambiguity for $F=1$ manifests itself in that only in this case are both integers.
$endgroup$
– Will Orrick
Apr 29 '13 at 6:29
add a comment |
$begingroup$
The second term vanishes quite quickly. We have $F_n=lfloor frac{phi^n}{sqrt{5}}+frac{1}{2}rfloor$, where $lfloor cdot rfloor$ denotes the floor function. If the floor weren't there, you could solve for $n$, and if you rounded you would be wrong only for possibly very small $n$.
Update: A quick calculation shows that $n=left[ log_phi sqrt{5}(F_n-frac{1}{2}) right]$ holds for all $nge 3$, and fails for $n=1,2$. In this case $[cdot]$ denotes the rounding function, or $[x]=lfloor x+frac{1}{2}rfloor$.
answered Apr 28 '13 at 0:36
vadim123vadim123
76.5k897191
$endgroup$
$begingroup$
This isn't what I'm looking for. I want something exact.
$endgroup$
– Linus
Apr 28 '13 at 0:45
$begingroup$
What do you mean by exact? The expression above yields an integer that is the desired integer for all $n$ except $n=1,2$. You can take it $pmod{2}$ to answer your even/odd question as well.
$endgroup$
– vadim123
Apr 28 '13 at 0:49
$begingroup$
By exact, I mean that I want a general formula that doesn't fail at all. Even setting aside the failure, if you put 3 into that second expression you get 3.5764. Even taking into account that 4 should be added and not subtracted in my almost-correct initial formula, the result is 3.9075. If you add 4 the result is exactly 4.
$endgroup$
– Linus
Apr 28 '13 at 1:32
1
$begingroup$
See en.wikipedia.org/wiki/…
$endgroup$
– lhf
Apr 28 '13 at 1:58
2
$begingroup$
@Linus: vadim123’s formula gives the exact value for all $nge 3$.
$endgroup$
– Brian M. Scott
Apr 28 '13 at 9:29
|
show 1 more comment
$begingroup$
The second term vanishes quite quickly. We have $F_n=lfloor frac{phi^n}{sqrt{5}}+frac{1}{2}rfloor$, where $lfloor cdot rfloor$ denotes the floor function. If the floor weren't there, you could solve for $n$, and if you rounded you would be wrong only for possibly very small $n$.
Update: A quick calculation shows that $n=left[ log_phi sqrt{5}(F_n-frac{1}{2}) right]$ holds for all $nge 3$, and fails for $n=1,2$. In this case $[cdot]$ denotes the rounding function, or $[x]=lfloor x+frac{1}{2}rfloor$.
answered Apr 28 '13 at 0:36
vadim123vadim123
76.5k897191
$endgroup$
$begingroup$
This isn't what I'm looking for. I want something exact.
$endgroup$
– Linus
Apr 28 '13 at 0:45
$begingroup$
What do you mean by exact? The expression above yields an integer that is the desired integer for all $n$ except $n=1,2$. You can take it $pmod{2}$ to answer your even/odd question as well.
$endgroup$
– vadim123
Apr 28 '13 at 0:49
$begingroup$
By exact, I mean that I want a general formula that doesn't fail at all. Even setting aside the failure, if you put 3 into that second expression you get 3.5764. Even taking into account that 4 should be added and not subtracted in my almost-correct initial formula, the result is 3.9075. If you add 4 the result is exactly 4.
$endgroup$
– Linus
Apr 28 '13 at 1:32
1
$begingroup$
See en.wikipedia.org/wiki/…
$endgroup$
– lhf
Apr 28 '13 at 1:58
2
$begingroup$
@Linus: vadim123’s formula gives the exact value for all $nge 3$.
$endgroup$
– Brian M. Scott
Apr 28 '13 at 9:29
|
show 1 more comment
$begingroup$
The second term vanishes quite quickly. We have $F_n=lfloor frac{phi^n}{sqrt{5}}+frac{1}{2}rfloor$, where $lfloor cdot rfloor$ denotes the floor function. If the floor weren't there, you could solve for $n$, and if you rounded you would be wrong only for possibly very small $n$.
Update: A quick calculation shows that $n=left[ log_phi sqrt{5}(F_n-frac{1}{2}) right]$ holds for all $nge 3$, and fails for $n=1,2$. In this case $[cdot]$ denotes the rounding function, or $[x]=lfloor x+frac{1}{2}rfloor$.
answered Apr 28 '13 at 0:36
vadim123vadim123
76.5k897191
$endgroup$
The second term vanishes quite quickly. We have $F_n=lfloor frac{phi^n}{sqrt{5}}+frac{1}{2}rfloor$, where $lfloor cdot rfloor$ denotes the floor function. If the floor weren't there, you could solve for $n$, and if you rounded you would be wrong only for possibly very small $n$.
Update: A quick calculation shows that $n=left[ log_phi sqrt{5}(F_n-frac{1}{2}) right]$ holds for all $nge 3$, and fails for $n=1,2$. In this case $[cdot]$ denotes the rounding function, or $[x]=lfloor x+frac{1}{2}rfloor$.
answered Apr 28 '13 at 0:36
vadim123vadim123
76.5k897191
edited Apr 28 '13 at 0:42
answered Apr 28 '13 at 0:36
vadim123vadim123
76.5k897191
answered Apr 28 '13 at 0:36
vadim123vadim123
76.5k897191
answered Apr 28 '13 at 0:36
vadim123vadim123
76.5k897191
76.5k897191
$begingroup$
This isn't what I'm looking for. I want something exact.
$endgroup$
– Linus
Apr 28 '13 at 0:45
$begingroup$
What do you mean by exact? The expression above yields an integer that is the desired integer for all $n$ except $n=1,2$. You can take it $pmod{2}$ to answer your even/odd question as well.
$endgroup$
– vadim123
Apr 28 '13 at 0:49
$begingroup$
By exact, I mean that I want a general formula that doesn't fail at all. Even setting aside the failure, if you put 3 into that second expression you get 3.5764. Even taking into account that 4 should be added and not subtracted in my almost-correct initial formula, the result is 3.9075. If you add 4 the result is exactly 4.
$endgroup$
– Linus
Apr 28 '13 at 1:32
1
$begingroup$
See en.wikipedia.org/wiki/…
$endgroup$
– lhf
Apr 28 '13 at 1:58
2
$begingroup$
@Linus: vadim123’s formula gives the exact value for all $nge 3$.
$endgroup$
– Brian M. Scott
Apr 28 '13 at 9:29
|
show 1 more comment
$begingroup$
This isn't what I'm looking for. I want something exact.
$endgroup$
– Linus
Apr 28 '13 at 0:45
$begingroup$
What do you mean by exact? The expression above yields an integer that is the desired integer for all $n$ except $n=1,2$. You can take it $pmod{2}$ to answer your even/odd question as well.
$endgroup$
– vadim123
Apr 28 '13 at 0:49
$begingroup$
By exact, I mean that I want a general formula that doesn't fail at all. Even setting aside the failure, if you put 3 into that second expression you get 3.5764. Even taking into account that 4 should be added and not subtracted in my almost-correct initial formula, the result is 3.9075. If you add 4 the result is exactly 4.
$endgroup$
– Linus
Apr 28 '13 at 1:32
1
$begingroup$
See en.wikipedia.org/wiki/…
$endgroup$
– lhf
Apr 28 '13 at 1:58
2
$begingroup$
@Linus: vadim123’s formula gives the exact value for all $nge 3$.
$endgroup$
– Brian M. Scott
Apr 28 '13 at 9:29
$begingroup$
This isn't what I'm looking for. I want something exact.
$endgroup$
– Linus
Apr 28 '13 at 0:45
$begingroup$
This isn't what I'm looking for. I want something exact.
$endgroup$
– Linus
Apr 28 '13 at 0:45
$begingroup$
What do you mean by exact? The expression above yields an integer that is the desired integer for all $n$ except $n=1,2$. You can take it $pmod{2}$ to answer your even/odd question as well.
$endgroup$
– vadim123
Apr 28 '13 at 0:49
$begingroup$
What do you mean by exact? The expression above yields an integer that is the desired integer for all $n$ except $n=1,2$. You can take it $pmod{2}$ to answer your even/odd question as well.
$endgroup$
– vadim123
Apr 28 '13 at 0:49
$begingroup$
By exact, I mean that I want a general formula that doesn't fail at all. Even setting aside the failure, if you put 3 into that second expression you get 3.5764. Even taking into account that 4 should be added and not subtracted in my almost-correct initial formula, the result is 3.9075. If you add 4 the result is exactly 4.
$endgroup$
– Linus
Apr 28 '13 at 1:32
$begingroup$
By exact, I mean that I want a general formula that doesn't fail at all. Even setting aside the failure, if you put 3 into that second expression you get 3.5764. Even taking into account that 4 should be added and not subtracted in my almost-correct initial formula, the result is 3.9075. If you add 4 the result is exactly 4.
$endgroup$
– Linus
Apr 28 '13 at 1:32
1
1
$begingroup$
See en.wikipedia.org/wiki/…
$endgroup$
– lhf
Apr 28 '13 at 1:58
$begingroup$
See en.wikipedia.org/wiki/…
$endgroup$
– lhf
Apr 28 '13 at 1:58
2
2
$begingroup$
@Linus: vadim123’s formula gives the exact value for all $nge 3$.
$endgroup$
– Brian M. Scott
Apr 28 '13 at 9:29
$begingroup$
@Linus: vadim123’s formula gives the exact value for all $nge 3$.
$endgroup$
– Brian M. Scott
Apr 28 '13 at 9:29
|
show 1 more comment
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f374758%2fhow-can-i-find-an-inverse-to-the-binet-formula%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
please update your title and the text of your question. As written it suggests that you are seeking an inverse to the Binet formula.
$endgroup$
– vadim123
Apr 28 '13 at 1:35
$begingroup$
Closely related: math.stackexchange.com/questions/191920/fibonacci-nth-term
$endgroup$
– Erick Wong
Apr 28 '13 at 2:17
$begingroup$
None of those answers gives an exact inverse. And I do believe one is possible, because the Binet formula isn't perfect; if you put in 0 you get $frac{2sqrt{5}}{5}$.
$endgroup$
– Linus
Apr 28 '13 at 5:19
$begingroup$
And if you put in 2 you get $frac{75 + 282sqrt{5}}{620}$, not quite the same thing as 1.
$endgroup$
– Linus
Apr 28 '13 at 5:32
1
$begingroup$
@Linus: Or, you could have the wrong formula.
$endgroup$
– Hurkyl
Apr 28 '13 at 9:10