The Leapfrog Lemma allows for a modified form of induction, where - as the name suggests - the inductive step involves "leapfrogging" from one set to another and then back to the first. This lemma is primarily associated with sieve functions and the complements of the sets generated by such functions.
Taking Z as the set of integers and using the usual notation of Z+ as the set of positive integers, we have
Leapfrog Lemma. Let
f, g : (
Z+)
2 to
Z+ be given functions where
f has
range A and
g has range
B and suppose ∃
N ∈
Z+ such that the following conditions hold:
(i) ∀
u ∈
Z+ where
u >
N, specify the
interval Wu = [
u, 2u−1]. Then |
A∩
Wu| ≥ |
B∩
Wu|.
(ii) ∃
a, b ∈
Z+ :
f(a, b) = 2x ⇔ ∃
c, d ∈
Z+ :
g(c, d) = x.
(iii) ∃
z ∈
Z+ where
z >
N : ∀
a, b ∈
Z+,
f(a, b) ≠
z.
Then |Z+ \ A| = |Z+ \ B| = |Z|.
Essentially, the three properties say "(i): f always produces at least as many values as g within the specified interval;" (ii) is the Odd-Even Theorem; "(iii) there is a first value that is not attainable by the sieve function f." Once all three properties are satisfied, possibly starting above some base value, then the complements of the ranges A, B are guaranteed to be infinite in cardinality.
While it may not be immediately obvious, this lemma is directly the result of logical conclusions drawn from the Odd-Even Theorem. The proof of this lemma is almost obvious: note that we are given the "first value" by (iii), assume that a value exists that is unattainable by f, note that (i) causes another value to exist within a specific interval that is unattainable by g, and note that by (ii) this other value's double must be unattainable by f, and is further outside the specific interval that the assumed value is in. This proves that there are an infinite number of values unattainable by f, which by (i) proves the same for g. QED