$\newcommand{\fib}{\operatorname{Fib}}$Let $a_n$ be the number of times that the procedure computes $\fib(0)$ or $\fib(1)$ when computing $\fib(n)$; it’s straightforward to prove by induciton on $n$ that $a_n=\fib(n+1)$ for all $n\in\Bbb N$.
Clearly $a_0=1=\fib(1)$ and $a_1=1=\fib(2)$. Moreover, if $n\ge 2$, and $a_k=\fib(k+1)$ for $0\le k<n$, then
$$a_n=a_{n-1}+a_{n-2}=\fib(n)+\fib(n-1)=\fib(n+1)\;,$$
so $a_k=\fib(k+1)$ for $0\le k\le n$, and by induction we have $a_n=\fib(n+1)$ for all $n\in\Bbb N$.
Showing that the sequence grows approximately exponentially takes more work. It’s well-known that
$$\fib(n)=\frac{\varphi^n-\widehat\varphi^n}{\sqrt5}\;,$$
where $\varphi=\frac12\left(1+\sqrt5\right)$ and $\widehat\varphi=\frac12\left(1-\sqrt5\right)=-\frac1\varphi$. Now $$\left|\frac{\widehat\varphi}{\sqrt5}\right|\approx 0.2764\;,$$ so
$$\left|\fib(n)-\frac{\varphi^n}{\sqrt5}\right|=\left|\frac{\widehat\varphi}{\sqrt5}\right|^n<\frac12\;,$$
and $\fib(n)$ is therefore the integer closest to $\frac{\varphi^n}{\sqrt5}$:
$$\fib(n)=\left\lfloor\frac{\varphi^n}{\sqrt5}+\frac12\right\rfloor\;.$$
In particular, $\fib(n)\approx\dfrac1{\sqrt5}\varphi^n$, where $\varphi\approx1.618$. The approximation isn’t bad even for very small $n$; for instance, $\dfrac1{\sqrt5}\varphi^3\approx1.89$, while $\fib(3)=2$, and $\dfrac1{\sqrt5}\varphi^5\approx4.96$, while $\fib(5)=5$. By the time you get up to $n=12$, the approximation is about $144.0014$, as against $\fib(12)=144$.
