For-All-n Statements Without Recursive Structure — Prefer Direct, Not Induction

A common reflex in first-year proof courses is to reach for induction the moment you see the phrase "for all integers n". It feels like the right tool — induction is explicitly a "for all n" technique — and students trained on induction exercises often apply it on autopilot.

That reflex is wrong more often than it is right. Induction works when the statement has recursive structure — when "the truth of P(n+1) can be built out of the truth of P(n)." Many universal statements lack this structure entirely, and for them induction is not just slower than direct proof, it is awkward to even set up. The inductive step has nothing to build on because the statement for n+1 is not meaningfully related to the statement for n.

The cue to recognise is visual and takes about two seconds. Once you see it, the choice between direct and induction becomes automatic.

Two kinds of "for all n"

Hold the statement "for all integers n, P(n)" up against these two templates.

Template A — recursive structure present. The predicate P(n) is built from a sum, product, or chain that has one more term when you move from n to n+1.

1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}. (The sum has n terms; the n+1 version has one more.)
2^n > n. (Moving n \to n+1 doubles the left and adds 1 to the right — recursive.)
The number of subsets of an n-element set is 2^n. (The (n+1)-element case adds one element and doubles the subsets — recursive.)

Template B — no recursive structure. The predicate P(n) is a direct algebraic fact about a single expression in n. There is no "n+1 version is built from n version" relationship.

For all integers n, 3n + 6 is a multiple of 3.
For all integers n, n^2 - n is even.
For all integers n, n^2 + n + 1 is odd.
For all real numbers x, x^2 \geq 0.

In Template A, induction is natural because the (n+1) case is defined in terms of the n case. In Template B, the (n+1) case is a separate algebraic expression that has no dependency on the n case — so induction has nothing to build with.

Why induction fails cleanly on Template B: the inductive step needs to derive P(n+1) from P(n). But for a claim like "3n + 6 is a multiple of 3," the expression 3(n+1) + 6 = 3n + 9 is a multiple of 3 for its own reasons — and its reasons do not use the fact that 3n + 6 was a multiple of 3. You would write a "proof of the inductive step" that silently does a direct proof. Skipping the induction shell entirely is shorter and more honest.

The recognition cue

Before picking a technique, look at the predicate and ask: does it contain a sum, a product with a variable upper bound, or a count of something that grows with n?

Sums with n terms: \sum_{k=1}^{n} \dots
Products with n factors: \prod_{k=1}^{n} \dots
Counts like "the number of \dots is \dots" where the count depends on n
Expressions that chain, like "for any n objects, \dots holds"

If yes, induction is natural. The recursive shape is there.

If no — if the predicate is just an algebraic expression in n with no running sum or recursion — induction is the wrong tool. Direct proof will finish in one or two lines of algebra, without the ceremony of base case and inductive step.

A side-by-side comparison

case:

A worked contrast

Take the universal "for all integers n, n^2 - n is even."

Induction attempt. Base case: n = 0 gives 0 - 0 = 0, even. Inductive step: assume n^2 - n is even, show (n+1)^2 - (n+1) is even. Compute: (n+1)^2 - (n+1) = n^2 + 2n + 1 - n - 1 = n^2 + n = (n^2 - n) + 2n. By hypothesis, n^2 - n is even; 2n is even; sum is even. Done. But look at that inductive step — it re-used the inductive hypothesis purely cosmetically. The real work was the algebra "n^2 + 2n + 1 - n - 1 = (n^2 - n) + 2n," plus the separate fact "2n is even." If you simply factor the original: n^2 - n = n(n-1). One of n and n-1 is even (consecutive integers alternate), so the product is even. \blacksquare — one sentence, no base case, no inductive hypothesis.

The induction proof takes six lines. The direct proof takes one. The induction proof is not wrong, but it puts scaffolding around a fact that does not need scaffolding.

Why students over-reach for induction

Three habitual reasons, worth naming so you can resist them:

"For all n" reads as a signal for induction. It is not — it is a signal for any technique that handles universally quantified statements, which includes direct proof with an arbitrary n.
Induction feels more rigorous. It is not. A direct proof with an arbitrary n covers every case simultaneously, which is exactly what induction also does — just with less ceremony.
The teacher is "teaching induction." The teacher wants you to see when induction is the right tool. Using induction indiscriminately hides the recognition skill the chapter is actually training.

The two-second diagnostic

When you see "for all integers n, [expression or claim]$", ask:

Is there a running sum, product, or count inside the claim? If yes — induction.
Is there a recursive definition (like Fibonacci or a recurrence) inside the claim? If yes — induction.
Is the claim a single algebraic statement about n? If yes — direct proof, with n an arbitrary integer. Look for factoring, substitution, or parity arguments.

Defaulting to direct proof on Template B saves you half a page of boilerplate on every problem. The payoff is that your proofs become shorter, the algebra becomes visible, and the rare cases where induction is truly required become easier to spot precisely because they stand out.