The problem that I am thinking about is the following:
Suppose we have a graph G with n vertices. In this graph, every vertex is connected to each of the remaining vertices, forming 1 big clique of n vertices.
Which one of these two answers is the correct one, concerning the total amount of cliques in this graph:
Answer 1: The total amount of cliques in G is $\sum\limits_{k=3}^n \binom{n}{k} = 2^n - \frac{n^2}{2} - \frac{n}{2} - 1$, and is therefore exponential.
Answer 2: Cliques k > 3 vertices are comprised of multiple cliques with 3 vertices. Therefore there are always less cliques with k vertices than there are cliques with (k-1) vertices. This means an upper bound on the amount of cliques in G is $\binom{n}{3}*(n-3)$, since there can not be more higher order cliques with more vertices than 3, being comprised of multiple 3-vertex-cliques. This upper bound is clearly polynomial.
Somehow these 2 answers contradict each other, and I just can not seem to wrap my head around it.
Might someone be able to save my day?
Your first answer is correct; the second is wrong.
To address the intuition you have in your second answer, note that when going from, say, $3$-vertex to $4$-vertex cliques, there are $n-3$ ways to grow a $3$-vertex clique to $4$ vertices by adding a new vertex, but only $4$ ways to shrink a $4$-vertex clique to $3$ vertices.
When $n-3$ is large compared to $4$, we should expect each $3$-clique to extend to lots of different $4$-cliques (giving us lots more $4$-cliques than $3$-cliques), which is only partially compensated by the four different $3$-cliques inside a $4$-clique.
(Of course, if the host graph were not a complete graph, not all $n-3$ extensions of a $3$-clique would produce a valid $4$-clique, whereas all $4$-cliques always contain four $3$-cliques, so the balance can shift in sparser graphs.)
The same argument shows that as long as $k$ is small compared to $n$ (the tipping point is $k = \frac n2$), we expect more $(k+1)$-cliques than $k$-cliques.