Fibonacci trick
I'm working on a video, tying the Fibonacci sequence into the general subject of difference equations.
Here's a fun trick: take any two consecutive numbers in the Fibonacci sequence, say 34 and 55. Now negate one and use them as the seed for the Fibonacci sequence, larger magnitude first, i.e.
$-55, 34, \cdots$
Carry it out, and you'll eventually get the Fibonacci sequence, or it's negative:
$-55, 34, -21, 13, -8, 5, -3, 2, -1, 1, 0, 1, 1 \cdots$
This is NOT a general property of difference equations -- it's part of the "magic" of this particular sequence.
- Comments
- Write a Comment Select to add a comment
Very interesting. Can you provide a proper mathematical proof of this? Has it already been done? A spreadsheet on this is easy to prepare.
The simplest proof would be this:
If A + B = C, then it must satisfy C - B = A :)
If you multiply by -1 the left side of the series looking from 0, you'll see that it's nothing else but traversing back the Fibonacci series. It must come to the first element eventually.
Thanks for that. I've kind of set this video aside for the moment in favor of more grungy practical stuff. So you've delivered the proof that I'm too lazy to provide...
Just out of curiosity, though, for a more general difference equation, can you generalize the proof so that it still uses simple arithmetic, yet gets the right answer? E.g., for a difference equation of the form \( x_n = a_1 x_{n-1} + a_2 x_{n-2} \) can you come up with something so simple?
Proof will be in the video. Basically, if you solve the difference equation that describes the sequence you get \( f \left ( k \right ) = A_1 d_1^k + A_2 d_2^k \), where \(d_1 = -\frac{1}{d_2} \) and \( A_1 = -A_2 \). With a bit more work you can show that it Must be True.
To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.
Please login (on the right) if you already have an account on this platform.
Otherwise, please use this form to register (free) an join one of the largest online community for Electrical/Embedded/DSP/FPGA/ML engineers:
