Exponential blowup in Simple Proof of a theorem of Statman by Mairson
Ok, I think I've got it.

$eq_{k+1}$ calls (indirectly) $eq_k$, so, if I call $subset_{k+1}$ twice, I fall in an exponential blowup because of the two recursive calls of $eq_k$: it is simple to see with a "linear recurrence relation of constant order".