The motivation for this question comes from recursions found in Ramsey theory. The Ramsey number $R(s,t)$ is equal to the minimum $n$ such that for any red-blue coloring of the edges of some $K_n$, one is guaranteed to be able to find some red $K_s$-subgraph of $K_n$ or some blue $K_t$-subgraph of $K_n$. To show that $R(s,t)$ is finite, it is common to prove the recursion $R(s,t) \leq R(s-1,t) + R(s,t-1)$ (see for example the proof in the Wikipedia for Ramsey's theorem).
By induction, one can prove multiple bounds using this recursion. Two examples of such bounds are $$R(s,t) \leq 2^{s+t} \quad \text{and} \quad R(s,t) \leq \binom{s+t-2}{s-1}.$$
While thinking about a finite version of the canonical Ramsey theorem, I have come across another recursion. Namely for some function $f(t)$, we have the recursion $f(t)\leq f(t-1)^2$. It is not difficult to show (again by induction) that $$f(t) \leq 2^{2^t}.$$ My main curiosity: Given that there are multiple bounds for $R(s,t)$ by a single recursion, are there are there other/better upper bounds we can prove for $f(t)$ using this recursion? More generally, given some recursion such as this, is there a way to prove that some upper bound is "as good as possible"? If not, I'd be quite curious as to why.
One cannot, in fact, prove any bounds using the recursion alone. Bounds like $R(s,t) \le 2^{s+t}$ and $R(s,t) \le \binom{s+t-2}{s-1}$ are shown by a combination of the inequality $R(s,t) \le R(s,t-1) + R(s-1,t)$ and some base cases. What we can prove depends on the base cases we assume.
In the case of Ramsey numbers, the most we can say without any hard work is that $R(s,2) = s$ and $R(2,t) = t$. If you color the edges of $K_s$ red and blue, either you get a blue $K_2$ (a blue edge) or the entire $K_s$ is red.
We can figure out the best thing we can prove using only the information above. To do so, define an upper bound $U(s,t)$ by the initial conditions $U(s,2)=s$ and $U(2,t)=t$. Then, for $s>2$ and $t>2$, define $U(s,t)$ to be equal to $U(s,t-1)+U(s-1,t)$. We can conclude that $R(s,t) \le U(s,t)$ for all $t$. But we are now in a position to determine what $U(s,t)$ is equal to, and we can derive the closed form $U(s,t) = \binom{s+t-2}{s-1}$. Therefore $R(s,t) \le \binom{s+t-2}{s-1}$ (for all $s,t \ge 2$) is the best thing we can prove without bringing in any additional facts about Ramsey numbers.
But, for example, suppose that we somehow proved that for all $t \ge 3$, $R(3,t) \le \frac{14}{15} \binom{t+2}{2}$. (I'm not sure if this is something we know.) Then we would be able to use the same method to prove that $R(s,t) \le \frac{14}{15}\binom{s+t-2}{s-1}$ for all $s,t \ge 3$.
Similarly, if we have $f(t) \le f(t-1)^2$, then we can prove that $f(t) \le f(0)^{2^t}$, and if $f(0) = 2$, then the best thing we can prove from that information is that $f(t) \le 2^{2^t}$. If it happens to be true that $f(2)=11$, then the best thing we can prove from there is $f(3) \le 11^2$, $f(4) \le 11^4$, $f(5) \le 11^8$, and in general $f(t) \le 11^{2^{t-2}}$. All these bounds are of the form $a \cdot b^{2^t}$, but the exact values of $a$ and $b$ depend on what initial conditions you can prove.