It is common wisdom that "When you see $\pi$, there is a circle close at hand". For example:
The periods of sine and cosine equal $2\pi$? Properly constructed, the right triangles that define them trace out a circle.
$e^{i\pi} = -1$? An artifact of polar complex coordinates.
The factor of $4\pi$ in Coulomb's Law? The electric force is spherically symmetric.
This makes sense, as $\pi$ is the ratio between a circle's circumference and its diameter.
Similarly, the golden ratio $\phi = \frac{1+\sqrt{5}}{2}$ is the ratio between a regular pentagon's diagonal and its side, and the two do seem to go hand in hand:
The Penrose tiling, composed of golden ratio kites and darts, is pentagonally symmetric.
The icosahedron and dodecahedron have pentagons in their structure, either vertex figures or faces, and are riddled with $\phi$s.
To construct a golden rectangle, you need to construct an angle that is $\frac{1}{5}$ of a turn, which is also how you start the construction of a regular pentagon.
However, the golden ratio is also found in the Fibonacci sequence as the limit of the ratio between adjacent terms. And there are plenty of cases where $\phi$ pops up because of this: Whythoff's nim, Lucas sequences, coverings with mono- and dominoes.
So now the question is Where's the pentagon in the Fibonacci sequence? Or is it that there's a Fibonacci sequence in the pentagon?
It's been long enough, time to accept an answer. mr_e_man's 'proof without words' is exactly what I'm looking for, so he gets the tick. That said, everyone's answers here were useful, especially as they reminded me that the pentagon in the Fibonacci sequence would only be approximate. Pointing this out is why I'm adding this rather than just clicking the tickmark.
Best Answer
Promoting my comment and image explanation into an answer.
The Fibonacci numbers themselves don't readily appear in a pentagon/pentagram, but the golden ratio and the same recurrence relation do show up. As always, the starting point is the golden triangle — an isosceles triangle with respective angles $2\pi/5$, $2\pi/5$ and $\pi/5$:
We have two similar triangles here leading to the familiar equation. If the length of the blue line is $1$ unit and the length of the red line is $x$, then the big isosceles triangle shows that the black line segment has length $1+x$. But, the similarity of the two triangles yields $x^2$ for that length. Hence $$x^2=1+x,\tag{1}$$ from which we can solve $x=\phi=(1+\sqrt5)/2.$
We can always draw a pentagram inside a regular pentagon by including the diagonals. But, by extending the sides of the same pentagon until they meet, we get another pentagram. Joining its star points gives us a bigger pentagon, and we can keep going like in the following image:
Observe that we could equally well look at the smaller pentagon bordered by the diagonals of a bigger one, draw its diagonals to form a smaller pentagram et cetera.
Anyway, it is easy to calculate the angles that appear in these recursive drawings, and see that they form a sequence of similar triangles. It follows that each pentagon (resp. pentagram) is a scaled up version of the preceding one by a factor of $\phi^2$. We also see that the lengths of consecutive segments forming the red zigzag are sides of isosceles triangles similar to the earlier one. Hence their lengths $\ell_0,\ell_1,\ldots$ all satisfy $\ell_{n+1}/\ell_n=\phi$, and thus satisfy the Fibonacci recurrence: $$\ell_n=\ell_{n-1}+\ell_{n-2}.$$
This is somewhat unsatisfactory because the Fibonacci numbers $F_n$ themselves don't show up — only the recurrence relation. We all know that, by Binet's formula, the numbers $F_n$ need a (small) correction term involving powers of the other root $-1/\phi$ of the equation $(1)$.
This discrepancy has been a source of recreational mathematics: Missing square puzzle, locally here and here. The idea is explained in the following image
On the left we have a square of side length $\phi^2$ subdivided into four polygons in such a way that the vertical as well as the horizontal sides have lengths $1,\phi$ or $\phi^2$. Those polygons can then be perfectly rearranged to form a rectangle of dimensions $\phi\times\phi^3$. All due to the identity $\phi^2=1+\phi$.
The missing square puzzles then emerge when we use consecutive Fibonacci numbers instead of consecutive powers of $\phi$ as lengths. Below see the version with respective side lengths $3,5,8$.
The four polygons in it would, again, form a nice $8\times8$ square, but narrowly fail to fill up a $13\times5$ rectangle. Just as well, given that $13\cdot5=8\cdot8+1$. Drawning it coarsely enough the puzzle designers can make that thin gap disappear! Using larger consecutive Fibonacci numbers makes the gap look thinner, but it always exists. All because we have the identity $$F_nF_{n+2}=F_{n+1}^2\pm1$$ with the sign alternating according to the parity of $n$ (and the indexing of the Fibonaccis).