Along with the binomial coefficients, the other two infinite families each enjoy a fairly simple recurrence. for example $$f(n,m)=\frac{(2n)!(2m)!}{n!(n+m)!m!}.$$ has $f(0,t)=\binom{2t}{t}$ and $f(i+1,j)=4f(i,j)-f(i,j+1).$
Consider the one parameter family $$\frac{(2n)!(6n)!}{n!(4n)!(3n)!}.$$ Viewed in isolation it seems hard to establish integrality without referring to the p-order formula. However as the case m=3n of the family $f(n,m)$ it is the values in a line of cells with slope 3.
I've wondered if any of the various "sporadic" one parameter families can be embedded in a similar manner in a 2 parameter family defined by a recurrence. Evidently the entire table would not all be given by a formula exactly of that form.
Perhaps an example of the kind of circularity you mention
arises with the self-reference phenomenon that arises in
connection with the incompleteness
theorems
and related applications. Specifically, Gödel proved
the fixed-point lemma that for any assertion $\varphi(x)$
in arithmetic, there is a sentence $\psi$ such that PA, or
any sufficiently powerful and expressible theory, proves
that $\psi$ is equivalent to
$\varphi(\ulcorner\psi\urcorner)$. In other words, $\psi$
is equivalent to the statement "$\psi$ has property
$\varphi$." Thus, statements in the language of arithmetic
can refer to themselves, and so self-reference, the stuff
of paradox and nonsense, enters our beautiful number
theory.
One famous example, used by Gödel to prove the first
incompleteness theorem, occurs when $\varphi(x)$ asserts,
"$x$ is the code of a statement having no proof in PA", for
then the resulting fixed point $\psi$ effectively asserts
"this statement is not provable". It follows now that it
cannot be provable, for then it would be a false provable
statement, and so it is true. Thus, it is a true unprovable
statement, establishing the first incompleteness theorem.
A dual version of this, however, exhibits your circularity
property in a stronger way. Namely, let us apply the fixed
point lemma to the formula $p(x)$ asserting "$x$ is the
code of a statement provable in PA." In this case, the
resulting fixed point $\psi$ asserts "this statement IS
provable." Consider now the following theorem of Löb:
Theorem.(Löb) If the Peano Axioms (PA) prove the implication (PA proves
$\varphi$)$\to\varphi$, then PA proves $\varphi$
directly.
(And the converse is immediate, so PA proves that (PA
proves $\varphi$)$\to \varphi$ if and only if PA proves
$\varphi$.)
In the case of $\psi$ asserting "$\psi$ is provable," we
have that the hypothesis of Löb's theorem holds, and
so we may make the conclusion that yes, indeed, $\psi$
really is provable! In other words, the statement "this
statement is provable" really is provable, although no
naive argument will establish this.
The proof of Löb's theorem is itself a surprising
exercise in circularity, something like the following:
Theorem. Santa exists.
Proof. Let $S$ be the statement, "If S holds, then Santa
exists." Now, we claim that $S$ is true. Since it is an
implication, we assume the hypothesis, and argue for the
conclusion. So assume that the hypothesis of S is true;
that is, assume $S$ holds. But then the implication
expressed by $S$ is true. So the conclusion that Santa
exists is also true. So we have shown under the assumption
of the hypothesis of $S$ that the conclusion is true. So we
have established that $S$ holds. Now, by $S$, it follows
that Santa exists. QED
(Those who know the proof of Löb's theorem will agree
that the proof is fundamentally the same as the above,
except that it is fully rigorous nonsense instead of silly
nonsense!)
Best Answer
Bertrand's Postulate follows as a direct consequence of the following theorem of J.J. Sylvester:
Theorem (Sylvester, 1892): Let $k$ be a positive integer. Then at least one of any $k$ consecutive integers greater than $k$ is divisible by a prime greater than $k$.
(For comparison: Chebyshev's analytic proof dates to 1850; Erdos' elementary proof dates to 1932.)
See Theorem 6 (p. 6) in http://www.math.sc.edu/~filaseta/papers/schurpaper.pdf, from which I quote:
"The theorem implies immediately that for any positive integer $k$, one of $k+1, k+2, \ldots, 2k$ is a prime (since one of these integers must be divisible by a prime $\geq k+1).$"
A copy of the Sylvester paper can be found here.
Edit: An article in the AMM (Aug/Sept, 2013) presents a revised version of Ramanujan's proof of Bertrand's Postulate; in particular, in which the use of Stirling's formula is eliminated. The citation is:
Ramanujan’s Proof of Bertrand’s Postulate. Jaban Meher, M. Ram Murty. The American Mathematical Monthly, Vol. 120, No. 7 (August–September 2013), pp. 650-653. http://www.jstor.org/stable/10.4169/amer.math.monthly.120.07.650.