2
$\begingroup$

The Fibonacci function I have constructed is:

f[n_] := f[n] = f[n - 1] + f[n - 2]

f[0] = 0; f[1] = 1;

with the first 20 values of the Fibonacci

Array[f, 20]

I would like to compute the 5th value of the Fibonacci but with the aid of the Trace function. However, I dod not understand the role of this function. No proper/ in depth explanation has been provided by Mathematica.

Any help is appreciated.

Edit:

enter image description here

$\endgroup$

2 Answers 2

5
$\begingroup$

You just apply Trace to the expression you want to see.

Clear[f]
f[n_] := f[n] = f[n - 1] + f[n - 2]
f[0] = 0; f[1] = 1;
Trace[f[3]]

enter image description here

What may be confusing you is the memoization. The code stores the values in a table the first time they are computed. Thus, if you ask for

Trace[f[3]]
{f[3],2}

a second time, you only get a terse response. This is why I added the Clear at the front.

$\endgroup$
9
  • $\begingroup$ Hi bill, why is there a hold in the output? $\endgroup$
    – Physkid
    Mar 26, 2017 at 13:50
  • $\begingroup$ I see no Hold... try running with a new kernel since that may be due to old definitions. $\endgroup$
    – bill s
    Mar 26, 2017 at 13:51
  • $\begingroup$ I have edited the OP with a shot of the "hold" $\endgroup$
    – Physkid
    Mar 26, 2017 at 13:54
  • $\begingroup$ Copy-paste my code (and change the 3 to a 5 if you wish). There is no Hold. You need to restart the kernel. You have some lingering definitions. $\endgroup$
    – bill s
    Mar 26, 2017 at 13:57
  • $\begingroup$ Is there a way to modify my above code to utilise dynamic programming to compute the 200th value of the Fibonacci sequence? $\endgroup$
    – Physkid
    Mar 26, 2017 at 14:05
4
$\begingroup$

This is an extended comment rather than an answer

ClearAll[f];

Using RSolve

RSolve[
 {f[n] == f[n - 1] + f[n - 2], f[0] == 0, f[1] == 1},
 f[n], n]

(*  {{f[n] -> Fibonacci[n]}}  *)

The Fibonacci function is

Fibonacci[n] // FunctionExpand

(*  ((1/2 (1 + Sqrt[5]))^n - (2/(1 + Sqrt[5]))^n Cos[n π])/Sqrt[5]  *)

Looking at the expression for GoldenRatio

GoldenRatio // FunctionExpand

(*  1/2 (1 + Sqrt[5])  *)

Then

Fibonacci[n] == (GoldenRatio^n - GoldenRatio^-n Cos[n Pi])/Sqrt[5] 
   // FunctionExpand

(*  True  *)

The recursive definition of the sequence for both positive and negative n is

f[0] = 0;
f[1] = 1;
f[n_?Positive] := f[n] = f[n - 1] + f[n - 2];
f[n_?Negative] := f[n] = f[n + 2] - f[n + 1];

Demonstrating that the sequence lies on the Plot of the Fibonacci function

Plot[Fibonacci[n], {n, -5.2, 5.2},
 Epilog -> {Red, AbsolutePointSize[6],
   Point[{#, f[#]} & /@ Range[-5, 5]]}]

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.