Negafibonacci numbers?
The Fibonacci numbers are given by
- F ( 0 ) = 0
- F ( 1 ) = 1
- F ( n ) = F ( n − 1 ) + F ( n − 2 ) .
So, the first few are 0 , 1 , 1 , 2 , 3 , 5 , 8 , 1 3 .
If we generalize this to negative numbers, what is F ( − 8 ) ?
The answer is -21.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Log in to reply
Seems to be; no formal proof but I am 99.9999% sure :P
Log in to reply
Yes, its true... Proof by induction...
Consider postive n .
Its trivially true for − n = 0 and − n = − 1 . Assume its true for F − n + 1 and F − n + 2 , and we will show its true for F − n
-
F − n = F − n + 1 − F − n + 2 (as we saw above)
-
F − n = ( − 1 ) n F n − 1 − ( − 1 ) n + 1 F n − 2
-
F − n = ( − 1 ) n + 1 ( F n − 1 + F n − 2 )
-
F − n = ( − 1 ) n + 1 F n
-
QED
In general,
F ( n ) = F ( n − 1 ) + F ( n − 2 )
so you can calculate backwards by saying:
F ( n − 2 ) = F ( n ) − F ( n − 1 )
This gives,
And in general,
F − n = ( − 1 ) n + 1 F n
Here is a quick proof by induction...
Consider postive n .
Its trivially true for − n = 0 and − n = − 1 . Assume its true for F − n + 1 and F − n + 2 , and we will show its true for F − n
F − n = F − n + 1 − F − n + 2 (as we saw above)
F − n = ( − 1 ) n F n − 1 − ( − 1 ) n + 1 F n − 2
F − n = ( − 1 ) n + 1 ( F n − 1 + F n − 2 )
F − n = ( − 1 ) n + 1 F n
QED
So,
F ( − 8 ) = − F ( 8 ) = − 2 1