We have all been there, when a formula works for the first 30 parameters,
but it is not sufficient for a proof. My question is where one can actually just check a finite number of cases, to conclude that a formula is correct.


That is, let $f,g : S \to \mathbb{N}$ be two functions from some (infinite) set $S$,
say the natural numbers, or permutations, graphs, etc. Assume that $f$ and $g$
are not too complicated (some measure of complexity here is needed, or they belong to some special family). 


**What types of theorems are there of the form $f(S\_k)=g(S\_k)$ for $k=1,2,\dots,\max \{ C(f), C(g) \}$ implies $f \equiv g$?** Here, the $S\_k$ are members of $S$ in some natural order, and $C$ is some measure of complexity.


*Example:* If $f,g$ are polynomials with integer coefficients, 
then we can take $C$ to be the degree of the polynomial. 


Another example (which is a conjecture) is the following:
Let $p,q$ be permutation patterns of length $k$.
Then, is there some $N(k)$ such that if $|S\_n(p)|=|S\_n(q)|$ for all $n\leq N(k)$,
such that $|S\_n(p)|=|S\_n(q)|$ for all $n$? It is conjectured that $N(k)=2k+1$ works.


Here, $S\_n(p)$ is all permutations avoiding the pattern $p$.


A third example, I think, is Zeilbergers algorithm, which proves combinatorial identities by testing a finite number of cases. (Zeilberger is a big fan of this type of proofs, if I am to believe his opinions on his personal web page.)



Results where complexity bounds implies finite number of test cases
I think that most of the answers to this [MO question](https://mathoverflow.net/questions/112097/important-open-problems-that-have-already-been-reduced-to-a-finite-but-infeasibl/112131#112131) are examples that you are looking for.
I'll rehash my own answer there in your language so that you can see what I mean. 


Let $f$ be the function which maps finite graphs to $\{0,1\}$, where $f(G)=1$ if and only if $G$ has no $K\_{t+1}$-minor but $G$ is not $t$-colourable. That is, $G$ is a counterexample to Hadwiger's Conjecture for $t$. Let $g$ be the function which is identically 0 for all finite graphs. 


Reed and Kawarabayashi proved that for every fixed $t$, there is a computable function $C(t)$, such that every minimal counterexample to Hadwiger's Conjecture for $t$ has at most $C(t)$ vertices. You can think of this as the *complexity* of $f$. Now just sort the set of graphs according to the number of vertices, and stop when you have tested all graphs up to $C(t)$ vertices. If $f(G)=0$ for all such graphs, you can conclude that $f=g$. 


