fibonacci

[Valmont]

Wowow what made you think "inverse fibonacci" is to be interpreted as the "inverse" like on the calculator?
The definition we now need is: Fn = (Fn-1) - (Fn-2)
This is a completely different concept!
The name is merely arbitrary.

That was an axiom. It doesn't make sense to prove that by the definition of an axiom obviously. However, we would like to proof Binet's formula to gain insight in what this all means.

Let P be...
(1 + sqrt(5))/2
and P' be...
(1 - sqrt(5))/2
This looks familiar
You must realize that these are the roots of x^2 -x -1 = 0 !!!

This way Binet's formula can be easely written (on this forum since we have no math symbols) as:
Un = F(n) = [1/sqrt(5)] * (P^n - P'^n)

Now substitute x for P. So we are dealing with P^2 - P -1 = 0.
From here it's easy to see (basic algebra) that this is the same as P^2 = P+1.
Let's generate a sequence and see what kind of a sequence we get:
P3 = P2 + P = P + 1 + P = 2P + 1
P4 = 2P2 + P = 2(P + 1) + P = 3P + 2
P5 = 3P2 + 2P = 3(P + 1) + 2P = 5P + 3
P6 = 5P2 + 3P = 5(P + 1) + 3P = 8P + 5
... so we get a Fibonacci sequence.
Thus we can rewrite the sequence in one single forumula:
Pn = F(n) . P + F(n-1)
But we have P' as well so we need to write that term as well:
P' n = F(n) . P' + F(n-1)

But...
P - P' = sqrt(5)

So from the original sequence we had:
Pn - P' n = F(n) . P - F(n) . P' = F(n) . (P - P') =>
F(n) = (Pn - P' n) / (P - P')

we can rewrite the sequence (thanks to the sqrt(5)) as:
Un = F(n) = [1/sqrt(5)] * Pn - P'n

So this whole demonstration shows that "inverso/inverse" is a different concept.

So now we can use our code freely:

#include <iostream>
#include <cmath>

using namespace std;

//use this round formula if your compiler doesn't have a round function built in.
/*
unsigned round(double x) 
{
return int(x + 0.5);
}
*/

unsigned int fib(int n)
{
  if(n == 0 || n == 1)
  {
    return n;
  }
  else
  {
    return fib(n - 1U) + fib(n - 2U);
  }
}

//-----------------------------

unsigned invfib(int n)
{
  if( n < 2 )
  {
    return n;
  }
  return unsigned(round((log(n) + log(5)/2) / log((1+sqrt(5))/2)));
}

//-------------------------------

bool isfib(unsigned n)
{
  return n == fib(invfib(n));
}


int main()
{
  std::cout<<fib(20)<<endl;
  std::cout<<invfib(6765)<<endl;
  
  return 0;
}

P.S.
Watch lower bounds huh .

[josh2two]

redhead, how would you recommend doing it?

[Valmont]

Without Binet there's only the cannonical form left:
Generate Fibonacci numbers until one of them matches your number. In that case your original number was part of the Fibonacci series. If the generated numbers are at one point bigger then your test value (but no match ever occured) then your test value never was a fiib-number.

I'm affraid there is no "inbetween" solution.