Fibonacci

[Harmon]

How would I make the nspire give me the nth Fibonacci number?

Thanks!
Kara

[Andy Kemp]

The quickest way is to enter a sequence plot as:

u1(n) = u1(n-1)+u1(n-2)

Initial terms:1,1

Then on any calculator page you can then find the nth Fibbonacci number by entering u1(20) etc...

[Rex Boggs]

Or you could use Binet's Formula:

   http://en.wikipedia.org/wiki/Fibonacci_number

(and scroll down a bit)

 

Cheers

 

Rex

[Andy Kemp]

Indeed - But using the closed form solution feels like cheating!

[Harmon]

Thanks to you both...my problem was not understanding I could have two
initial terms in the sequence plot. Ah ha!

Kara

On Oct 20, 3:10 pm, Andy Kemp <a...@1kemp.co.uk> wrote:
> Indeed - But using the closed form solution feels like cheating!
>

> On Tue, Oct 20, 2009 at 9:09 PM, Rex Boggs <rexbog...@optusnet.com.au>wrote:
>
>
>
> >  Or you could use Binet's Formula:
> >    http://en.wikipedia.org/wiki/Fibonacci_number
> > (and scroll down a bit)
>
> > Cheers
>
> > Rex
>

> > ----- Original Message ----- *From:* Andy Kemp <a...@1kemp.co.uk>
> > *To:* tins...@googlegroups.com
> > *Sent:* Wednesday, October 21, 2009 5:58 AM
> > *Subject:* [tinspire] Re: Fibonacci

>
> > The quickest way is to enter a sequence plot as:
> > u1(n) = u1(n-1)+u1(n-2)
> > Initial terms:1,1
>
> > Then on any calculator page you can then find the nth Fibbonacci number by
> > entering u1(20) etc...
>

> > On Tue, Oct 20, 2009 at 6:09 PM, Harmon <idom...@comcast.net> wrote:
>
> >> How would I make the nspire give me the nth Fibonacci number?
>
> >> Thanks!

> >> Kara- Hide quoted text -
>
> - Show quoted text -

[Andy Kemp]

The sequence plotting really is neat...

When I look at Fibonacci I like to also look at the golden ratio and show that the limit of the ratio of successive terms tends to the golden ratio...

The nice thing about doing this on the Nspire is if you have entered the Fibonacci sequence as u1 then you can make:

u2(n)=u1(n)/u1(n-1)

and see that this approaches (sqrt(5)+1)/2

Cheers

Andy

[Marc Garneau]

The other really cool thing about that ratio is that it doesn't matter what your first 2 terms are.  Change them from 1,1 to anything else (eg: root(2) and -5/4).  They still approach the limit.  Just don't use 0,0 for obvious reasons. I imagine it works for complex numbers too, but I haven't given that enough thought, nor have I tried it.  Or change the sequence to the sum of the first 3 terms, and you approach a different constant.  The fun never ends!!!!  Sorry for my enthusiasm, but I'm pretty sure I'm not the only math geek on this list :) 

In reference to the earlier messages:

Another non-'cheating' way is to generate the sequence on a spreadsheet, either manually, or using the "Generate Sequence" command.  The formula part ends up being the same (you get a dialog box prompting for u(n), so you just define it using u(n-1) + u(n-2)).  The initial terms are also prompted for.

The sequence mode graphing method that Andy mentioned works far better though, as it can easily be called from the calculator page.  To call a later term from the spreadsheet way, you need to define the list as a variable first.  It's also limited up to n=255, though you can change that in the syntax.

What's a bit peculiar is the spreadsheet understands a formula called seqn, e.g.: =seqn(u(n-1)+u(n-2),{1,1},500), but it only works for 'u', and it can't be used to define a variable on a calculator page.  But don't give up on the calculator page.  Using a program gives a cool difference:

Define fib(n)=

Prgm

  t:={1,1}

  For i,3,n

    t[i]:=t[i-1]+t[i-2]

  EndFor

  Disp t[n]

EndPrgm

The difference is that you get a full expression of the number, instead of the scientific notation.  For example, the 200th Fibonacci number is:

280571172992510140037611932413038677189525.

You could add the first 2 terms as parameters too, just by defining the program using something like fib(n,t1, t2).

Marc Garneau

[Nelson Sousa]

In a two term recursive sequence define

u1(n) = u1(n-1)+u1(n-2)
initial terms = 1,1

(having more initial terms means adding extra elements to the initial
values sequence, separated by commas).


On a spreadsheet you can also use the seqn function to generate a list
of the first n fibonacci numbers.

Cheers,
Nelson

[Andy Kemp]

Nice!  I did wonder why it only returned the approximate solution using the sequence plotter - It's nice to see that we can quickly find the exact value with a little bit of programming!

[Nelson Sousa]

About the mathematics of it all (which is quite beautiful - and fun!):

The difference between two consecutive terms is another term of the
Fibonacci sequence; in fact, it's equal to the previous term, that is
u(n)-u(n-1) = u(n-2).

So... they should be exponential!! (the reason is the same behind the
fact that any linear ODE of constant coefficients has exponential
solutions)


Now, lets write u(n) = k^n; we have
k^(n) = k^(n-1) + k^(n-2) <=> k^2 = k+1;
the solutions are Phi and -1/Phi = 1-Phi . So, we have two possible solutions,

u(n) = Phi^n
or
u(n) = (-1/Phi)^n

Which one is it? Well, the general solution will be a linear
combination of the two (linear coefficients => a linear combination of
solutions is still a solution), which means that

u(n) = A Phi^n - B/Phi^n

is the most general solution. We determine A and B with the initial conditions,
u(0)=0 and u(1) = 1, giving A=1/sqrt(5) and B=-A.

As -1/Phi is actually Phi-1, we can write

u(n) = 1/sqrt(5) * ( Phi^n - (1-Phi)^n ), which is the closed form
mentioned on Wikipedia.



As to the limit of the quotient: Phi>1 and 1/Phi <1, so in the limit
the term in (-1/Phi)^n goes to zero. Therefore, regardless (really?)
of the coefficients A and B, the quotient will always be Phi in the
limit. There are two obvious exceptions: when A=B=0 we have an
identically null sequence, and when A=0 and B isn't zero, we have

u(n) = B * (-1/Phi)^n, so the limit of the quotient is identically -1/Phi.

Take, for example, B=1; then we have

u(0) = 1
u(1) = -1/Phi.

So there's actually ONE situation in which the quotient is different,
which corresponds to a degenerate situation, where the quotient of the
two first elements is exactly one of the roots of the characteristic
equation. (the other degenerate case is when u(0)=1 and u(1)=Phi, in
which the quotient is also constant, identically equal to Phi).

So, Phi is a stable equilibrium while -1/Phi is an unstable
equilibrium. Anything exactly on the equilibrium points will remain
there while anything in between will be atracted by the stable points.

Now, a word of caution: the equilibrium at -1/Phi is quite unstable
and convergence to the stable equilibrium Phi is very, very fast. So
if any error is introduced into the algorithm, no matter how small,
you won't get to see that u(100)/u(99) = -1/Phi.

Don't even try to compute the quotient on the Nspire; the answer will
be approximate and convergence to the stable equilibrium is very, very
fast. So you won't get -0.618... but instead 1.618... This is because
even a small error of the magnitude of 10^-14 will propagate at an
incredible speed and within only 30 or 40 iterations the result
converges to the stable equilibrium point. The same happens even on
the Nspire CAS if you press Ctrl+Enter to compute a fast answer. The
only way you'll get the correct answer is if you compute it
simbolically and then copy&paste the result and approximate only the
final result. The same will happen on any software as long as you ask
for approximate answers too soon. (e.g., Mathematica 6 does the same).
Approximating the expansion of (1-Phi)^n is definitely not a good
idea.

Even increasing the precision would only mean that convergence to Phi
would be delayed... by a few iterations.

A lot more could be said about Fibonacci, convergence, the golden
ration, game theory, chaos and a lot more things that come up from a
simple rabbit problem, but... well this post is too long already.


Have fun exploring Fibonacci and his wonderful rabbits!



Nelson

[Eric Findlay]

You can actually do it in fewer lines with a recursive function:

Define fib(n)=
Func
if n=0 or n=1
return 1
else
return fib(n-2)+fib(n-1)
EndFunc

However, due to the use of memory for each instance of the function, it
can't calculate larger numbers (like 200), but it's good to use if
you're discussing algorithms and works quite well on the computer.

--
For I am convinced that neither death nor life, neither angels nor
demons, neither the present nor the future, nor any powers, neither
height nor depth, nor anything else in all creation, will be able to
separate us from the love of God that is in Christ Jesus our Lord.
- Romans 8:38-39 (NIV)
--
Eric Findlay
AKA Eagle-Man

> <mailto:a...@1kemp.co.uk>> wrote:
> > Indeed - But using the closed form solution feels like cheating!
> >
> > On Tue, Oct 20, 2009 at 9:09 PM, Rex Boggs

> <rexbog...@optusnet.com.au <mailto:rexbog...@optusnet.com.au>>wrote:

> >
> >
> >
> > > Or you could use Binet's Formula:
> > > http://en.wikipedia.org/wiki/Fibonacci_number
> > > (and scroll down a bit)
> >
> > > Cheers
> >
> > > Rex
> >
> > > ----- Original Message ----- *From:* Andy Kemp

> <a...@1kemp.co.uk <mailto:a...@1kemp.co.uk>>
> > > *To:* tins...@googlegroups.com
> <mailto:tins...@googlegroups.com>

> > > *Sent:* Wednesday, October 21, 2009 5:58 AM
> > > *Subject:* [tinspire] Re: Fibonacci
> >
> > > The quickest way is to enter a sequence plot as:
> > > u1(n) = u1(n-1)+u1(n-2)
> > > Initial terms:1,1
> >
> > > Then on any calculator page you can then find the nth
> Fibbonacci number by
> > > entering u1(20) etc...
> >
> > > On Tue, Oct 20, 2009 at 6:09 PM, Harmon
> <idom...@comcast.net <mailto:idom...@comcast.net>> wrote:
> >
> > >> How would I make the nspire give me the nth Fibonacci number?
> >
> > >> Thanks!
> > >> Kara- Hide quoted text -
> >
> > - Show quoted text -
>
>
>
>
>
>
> >
>
>
>

> No virus found in this incoming message.
> Checked by AVG - www.avg.com
> Version: 8.5.423 / Virus Database: 270.14.24/2449 - Release Date: 10/20/09 18:42:00
>

[Nelson Sousa]

actually fib(0)=0 and fib(1)=1 (the classical definition has
fib(1)=fib(2)=1, which gives the exact same result).

Nelson

[Andy Kemp]

Ah but this version varies serious philosophical questions about where the first rabbits came from!

[Nelson Sousa]

not really, it's equivalent to say u(1)=1 and u(2)=1, which respects
the sentence "on the first month there's 1 couple of rabbits". Saying
that your first month is n=0 means that the 10th month is u(9). I
prefer to say that the 10th month is u(10) :P

Cheers,
Nelson

[Gert]

Hi all,

Is it possible to define a recursive sequence and its initial values
directly in the calculator?
I.e. typing for example:

u1(n) = u1(n-1)+u1(n-2)
initial terms = 1,1

The problem is that the TI-Nspire does not accept initial values.

Kind regards,

Gert

[Nelson Sousa]

Yes, it is. You can use the "piecewise" template and define
u(n) = u(n-1)+u(n-2), n>=2
u(1)= 1
u(0)=1

See attached file with the sequence defined and some terms calculated.

Nelson

[Gert]

Nelson,

Great,
Thanks for answer and responsetime.

Kind regards,

Gert