Forced Induction Engine

Step 0

Assume a polynomial, with the unknowns named

The only leap in the method is the shape of the answer. Take the sum to be a polynomial in N with no constant term and degree one higher than the power being summed:

The coefficients c_i are unknowns. They are not guessed and not looked up — the two induction steps below generate exactly enough linear equations to pin every one of them down.

Step 1

Force the first case true

Set N = 1. The left side is 1ⁿ = 1 and every power of N on the right collapses to 1, so the whole ansatz reduces to a single normalization condition:

This is the base case of the induction. It turns out to be the same equation the gather in Step 2 produces at j = 0, so it is satisfied automatically — a useful redundancy, and a free consistency check on the solve.

Step 2

Force the step from N to N+1

Adding one more term to the sum adds (N+1)ⁿ. Demanding that the same polynomial still fit gives one equation, which after the Nⁱ terms cancel is pure binomial bookkeeping:

Expanding both sides and collecting like powers of N, the requirement that the identity hold for every N forces each coefficient to vanish separately. That is where the equations come from:

Step 3

The triangular system, already triangulated

Step 4

Back-substitution, top row first

Row j = n contains a single unknown, so it solves immediately; each row below it has one new unknown and known values everywhere else. Every value here is an exact rational.

The final row, j = 0, is the Step 1 condition Σc_i = 1. Its verdict is reported in the machine check below.

Result

The closed form

Factored

Evaluate it

The original question on the page was “what is the sum of the first 1000 numbers?” — answered here by the polynomial, and independently by brute-force addition.

Verification

Machine check: this really is a proof for this n

Forced induction is only a construction until the two induction clauses are confirmed on the polynomial it produced. Both are checked here exactly, in rational arithmetic — no floating point, no sampling:

Base case evaluates the polynomial at N = 1. Induction step forms P(N) − P(N−1) as an exact polynomial identity and compares it, coefficient by coefficient, with Nⁿ. Together these two facts are the whole induction; the spot checks that follow are redundant, and are there to catch a coding error rather than a mathematical one.

General solution

The system solves symbolically in n

The real power of the triangular form is that you never have to fix n at all. Solving the same rows with n left as a symbol produces a ladder of coefficients — and every second rung is zero:

Each rung is c_n−(2k−1) = B_2k · n(n−1)…(n−2k+2) / (2k)!, reduced. Read the ladder downward and stop at c₁: the rungs do not self-truncate, so a rung whose index falls below 1 is not part of the formula even though its expression is non-zero.

Identification

The last coefficient is a Bernoulli number

The N¹ coefficient of the n^th sum satisfies its own recursion, generated below from nothing but the triangular system:

The forced-induction recursion is the Bernoulli recursion with 1 − in place of −. Writing d[n] = c₁[n] − B_n, the difference of the two recursions is d[n] = 1 − Σ_k<nC(n+1,k) d[k]/(n+1) with d[0]=0, d[1]=1. Only d[1] is ever non-zero, so for n ≥ 2 it collapses to d[n] = 1 − C(n+1,1)/(n+1) = 0. The whole offset lands on B₁ and nowhere else — which is why c₁[n] = (−1)ⁿB_n holds with no exceptions at all.

Cross-check

Three independent routes to the same polynomial

The page gives three ways to build the coefficients. They share no code path here beyond the rational arithmetic, so agreement is a real check:

A solves the triangular system directly. B uses c_j+1[n] = c₁[n−j] C(n,j)/(j+1) with the Bernoulli ladder as input. C is the differencing route: integrate the (n−1)^th formula, multiply every term by n, then add the single term c₁[n] N that makes the coefficients sum to 1.

Output

Every sum from 0 up to n

Tangent

The same mechanism, run backwards

Forcing the step from N to N+1 is exactly a telescoping condition, so the identity that makes a sum collapse to a single power is the same binomial expansion read the other way:

Generated by expanding xⁿ − (x−1)ⁿ for the current n and summing it numerically over a range. The n ≥ 1 restriction is real: at n = 0 the x = 1 term needs 0⁰, which is why the published page carries a δ_x1-regularized version for the wider case.

Appendix A

Any arithmetic progression, by substitution

Once the sums of plain powers exist, no new machinery is needed for evens, odds, multiples, or multiples-plus-a-constant. Expand the bracket, then replace each Σx^k by the formula the engine already has:

Careful with what N counts: it is the number of terms, not the last one. With a = 2, b = −1 the final term is 2N − 1, so N = 50 sums the odd powers up to 99, not up to 50.

Appendix B

Telescoping that survives n ≤ 0

The plain telescoping identity needs n ≥ 1, because its first term asks for 0ⁿ. Absorbing the first term with a Kronecker delta removes that single obstruction and the identity then holds for every integer n — zero and negative included — and for any offset a ≥ 0:

Each cell sums the left side term by term in exact rational arithmetic for N = 1…6 and compares with (N+a)ⁿ. The plain column is the same identity without the delta, so its failures at n ≤ 0 are exactly what the regularization repairs. Two specializations worth naming: at n = −1, a = 0 the sum collapses to 1/N; at n = 0 it collapses to Σ δ_x1 = 1.

Appendix C

Closed forms that need no induction at all

These come from telescoping, a geometric ratio, or Pascal's identity rather than from a polynomial ansatz. Each row is checked exactly over the stated range:

The first two are the derivative-free telescopes 1/x − 1/(x+1) and 1/x² − 1/(x+1)². The last is the hockey-stick identity, which is what makes Appendix D work.

Appendix D

Sums of sums of sums, in closed form

Apply the summation operator repeatedly: f₁ is the N^th term, f₂ its running sum, f₃ the sum of those, and so on. Every one of them factors the same way — a rising product over a factorial, times a cofactor of degree one less than the power:

The cofactor is computed here, not quoted: the engine multiplies f_k,j by (k+j−1)!, divides by N(N+1)…(N+k−1) as exact polynomials, and reports the remainder. At j = 1 the cofactor is 1, giving f_k,1 = C(N−1+k, k). At j = 2 it is 2N + (k−1); at j = 3 it is 6N² + 6(k−1)N + (k−1)(k−2), i.e. 6N(N+k−1) + (k−1)(k−2). Beyond that the pattern is no longer tabulated anywhere — it is generated on demand.