Induct over the decreasing target. A rejection at $k+1$ bounds all independent sets by $k$, preserving the induction invariant. A success uses that invariant as the certified upper bound. Initially every independent set has at most the graph's order, and the zero case returns the empty set.