HINT: Notice that every fat subset of $\{1,\dots,n\}$ is automatically a fat subset of $\{1,\dots,n+1\}$; that accounts for $f(n)$ fat subsets of $\{1,\dots,n+1\}$, so you just need to show that there are $f(n-1)$ fat subsets of $\{1,\dots,n+1\}$ that are not already fat subsets of $\{1,\dots,n\}$. Clearly those must be the fat subsets of $\{1,\dots,n+1\}$ that include $n+1$. At this point it might not be a bad idea to collect some data by listing the fat subsets of $\{1,\dots,n\}$ for some small values of $n$:
$$\begin{array}{c|l}
n&\text{Fat subsets}\\ \hline
0&\varnothing\\
1&\varnothing,\{1\}\\
2&\varnothing,\{1\},\{2\}\\
3&\varnothing,\{1\},\{2\},\{3\},\{2,3\}\\
4&\varnothing,\{1\},\{2\},\{3\},\{2,3\},\{4\},\{2,4\},\{3,4\}\\
5&\varnothing,\{1\},\{2\},\{3\},\{2,3\},\{4\},\{2,4\},\{3,4\},\{5\},\{2,5\},\{3,5\},\{4,5\},\{3,4,5\}
\end{array}$$
Now try to match up the new sets on each line with the sets two lines back:
$$\begin{array}{c|l|c|l}
n&\text{Fat subsets}&n+2&\text{New fat subsets}\\ \hline
0&\varnothing&2&\{2\}\\
1&\varnothing,\{1\}&3&\{3\},\{2,3\}\\
2&\varnothing,\{1\},\{2\}&4&\{4\},\{2,4\},\{3,4\}\\
3&\varnothing,\{1\},\{2\},\{3\},\{2,3\}&5&\{5\},\{2,5\},\{3,5\},\{4,5\},\{3,4,5\}\\
\end{array}$$
If you stare at that table for a bit, you should be able to see how to derive the new fat subsets of $\{1,\dots,n+1\}$, the ones that aren’t fat subsets of $\{1,\dots,n\}$, from the fat subsets of $\{1,\dots,n-1\}$. Once you see it, proving that it’s correct isn’t too hard.
For $n>2$, in order to calculate $f(n)$ using this recurrence you must first calculate $f(n-1)$, which takes $c(n-1)$ additions, and $f(n-2)$, which takes another $c(n-2)$ additions, and then add the results, which takes one more addition. This will give you the desired recurrence for $c(n)$.
Once you have that, you want to prove or disprove that
$$c(n)\ge 2^{(n-2)/2}\tag{1}$$
for $n\ge 2$. At this point, if not earlier, it would be a good idea to calculate some values of $c(n)$. You should get the following values:
$$\begin{array}{rcc}
n:&2&3&4&5&6&7&8\\
c(n):&1&2&4&7&12&20&33
\end{array}$$
If you compare that bottom row with the corresponding values of $2^{(n-2)/1}$, you can make a pretty good guess that $(1)$ holds for $n\ge 2$. You can try proving it directly by induction, but it might be easier to take a detour.
Compare that bottom row with $f(n+1)$, and you can discover a formula for the $c(n)$’s in terms of $f(n)$’s, one that’s easily proved by induction on $n$. Then you can use the fact that the Fibonacci sequence is almost a geometric sequence with ratio $\varphi=\frac12(1+\sqrt5)$.
Best Answer
Computing
FIB(0)andFIB(1)has no additions, as it returnsn.Computing
FIB(n)has one addition, plus as many additions asFIB(n-1)andFIB(n-2)have.So, we have
$$a_n = \begin{cases} 0, & n \in \{0, 1\}, \\ a_{n-1} + 1 + a_{n-2}, & n > 1. \end{cases}$$
Now, use the mathematical induction to check that $a_n = F_{n+1} - 1$ and comment if you get stuck.