How to prove $\cos \frac{2\pi }{5}=\frac{-1+\sqrt{5}}{4}$?
Since $x := \cos \frac{2 \pi}{5} = \frac{z + z^{-1}}{2}$ where $z:=e^{\frac{2 i \pi}{5}}$, and $1+z+z^2+z^3+z^4=0$ (for $z^5=1$ and $z \neq 1$), $x^2+\frac{x}{2}-\frac{1}{4}=0$, and voilà.
Consider a $\triangle ABC$ with $AB=1$, $\mathrm{m}\angle A=\frac{\pi}{5}$ and $\mathrm{m}\angle B=\mathrm{m}\angle C=\frac{2\pi}{5}$, and point $D$ on $\overline{AC}$ such that $\overline{BD}$ bisects $\angle ABC$. Now, $\mathrm{m}\angle CBD=\frac{\pi}{5}$ and $\mathrm{m}\angle BDC=\frac{2\pi}{5}$, so $\triangle ABC\sim\triangle BCD$. Also note that $\triangle ABD$ is isosceles so that $BC=BD=AD$.
Let $x=BC=BD=AD$. From the similar triangles, $\frac{AB}{BC}=\frac{BC}{CD}$ or $\frac{1}{x}=\frac{x}{1-x}$, so $1-x=x^2$ and $x=\frac{\sqrt{5}-1}{2}$ (the other solution is negative and lengths cannot be negative).
Now, apply the Law of Cosines to $\triangle ABC$: $$\begin{align} \cos\frac{2\pi}{5}=\cos C&=\frac{a^2+b^2-c^2}{2ab} \\\\ &=\frac{\left(\frac{\sqrt{5}-1}{2}\right)^2+1^2-1^2}{2\cdot\frac{\sqrt{5}-1}{2}\cdot 1} \\\\ &=\frac{\frac{\sqrt{5}-1}{2} \cdot \frac{\sqrt{5}-1}{2}}{2\cdot\frac{\sqrt{5}-1}{2}} \\\\ &=\frac{\sqrt{5}-1}{4}. \end{align}$$
How about combinatorially? This follows from the following two facts.
The eigenvalues of the adjacency matrix of the path graph on $n$ vertices are $2 \cos \frac{k \pi}{n+1}, k = 1, 2, ... n$.
The number of closed walks from one end of the path graph on $4$ vertices to itself of length $2n$ is the Fibonacci number $F_{2n}$.
The first can be proven by direct computation (although it also somehow falls out of the theory of quantum groups) and the second is a nice combinatorial argument which I will leave as an exercise. I discuss some of the surrounding issues in this blog post.