Define Fibonacci numbers by
$\text {Fib(n)} = \begin{cases} 0 & \text{if $n = 0$} \\[2ex] 1 & \text{if $n = 1$} \\[2ex] \text {Fib(n - 1) + Fib(n - 2)} & \text {otherwise} \end{cases}$
My textbook goes on to say:
In fact, it is not hard to show that the number of times the procedure will compute (fib $1$) or (fib $0$) (the number of leaves in the above tree, in general) is precisely Fib($n + 1$).
To get an idea of how bad this is, one can show that the value of Fib$(n)$ grows exponentially with $n$.
No proof is given or asked to supply, so in the context of what Im studying they are not very important, but where can I look up the concepts necessary to prove these statements or just proofs themselves?
$\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$.