The principle of mathematical induction

Depends on

• The natural numbers $\mathbb{N}$ (von Neumann)
• Inductive set
• The natural numbers exist: a smallest inductive set

Used by

• ∑_k<n+1binomnk = 2ⁿ, and ∑_k<n+1(-1)ᵏιbinomnk = 0 for n ≥ 1 Corollary
• A finite row reduction from A to B is encoded by B=Eᵣ⋯ E₁A Corollary
• A polynomial ring in finitely many indeterminates over an integral domain is an integral domain Corollary
• A power-series sum is infinitely differentiable inside its radius and satisfies aₙ=f⁽ⁿ⁾(c)/ι(n!) at its centre Corollary
• A rational root of xᵏ = m is an integer: if k ≥ 1, m ∈ ℤ, x ∈ ℚ and xᵏ is the image of m, then x is the image of an integer Corollary
• Every nondegenerate interval of ℝ is uncountable Corollary
• If a prime p divides a finite product ∏_i<n aᵢ of integers then p ∣ aᵢ for some i < n; at n = 0 the product is 1 and the hypothesis cannot hold Corollary
• If V = bigoplus_i<n Uᵢ with every Uᵢ finite-dimensional, then V is finite-dimensional and dim_F V = ∑_i<n dim_F Uᵢ; in particular dim_F(U ⊕ W) = dim_F U + dim_F W Corollary
• ℝ((t⁻¹)) has the nested interval property for lengths tending to 0 Corollary
• The a priori bound d(x^*, xₙ) ≤ qⁿ d(x₁,x₀)/(1-q) and the a posteriori bound d(x^*, xₙ₊₁) ≤ q d(xₙ₊₁,xₙ)/(1-q) Corollary
• The extended Euclidean algorithm: the same descent produces integers x, y with ax + by = gcd(a,b), so Bézout coefficients are computed and not merely shown to exist Corollary
• ∏_j ≥ 0 (1 + (-1)ʲ/√j+2) has partial products tending to 0 although ∑_j ≥ 0 (-1)ʲ/√j+2 converges Counterexample
• A nonnegative non-monotone sequence for which ∑ aₖ and ∑ 2ᵏ a_2ᵏ behave differently Counterexample
• On a closed interval of ℚ there is a continuous unbounded function, a bounded one with no maximum, and one without the intermediate value property Counterexample
• xₖ₊₁ = xₖ + 1/xₖ from x₁ = 1 has strictly decreasing consecutive gaps and diverges, so no uniform c < 1 exists Counterexample
• Cliques, independent sets, clique number and independence number Definition
• Exponentiation of natural numbers, mⁿ, and its agreement with the integer power in ℝ Definition
• Finite sums and finite products of natural numbers, ∑_k<n aₖ and ∏_k<n aₖ in ℕ Definition
• Finite sums and finite products, by recursion Definition
• Grid partitions of a rectangle in ℝᵐ, their cells, refinements and mesh Definition
• Nondecreasing, increasing, nonincreasing, decreasing, monotone, and eventually monotone sequences Definition
• Partition of [a,b] as a finite strictly increasing list a = t₀ < t₁ < … < tₙ = b, its subintervals and their lengths, its mesh, refinement, and the common refinement of two partitions Definition
• Row space, column space, nullspace, row rank, column rank and matrix rank Definition
• The Cantor middle-thirds set as the intersection of the sets Cₙ obtained by removing open middle thirds Definition
• The discrete, indiscrete, cofinite, cocountable, particular-point and Sierpinski topologies Definition
• The dyadic rationals of [0,1], their finite levels Dₙ, and their density in [0,1] Definition
• The factorial n! and the falling factorial n^underlinek, defined by recursion in ℕ Definition
• The p-adic valuation vₚ(a) of a nonzero integer: the greatest k ∈ ℕ with pᵏ ∣ a Definition
• The product g₀ g₁ ⋯ gₙ₋₁ of a finite list in a monoid, by recursion, with the empty product (n = 0) equal to the identity Definition
• The Smith-Volterra-Cantor set: the same construction removing, at stage n ≥ 1, an open middle interval of length 4⁻ⁿ from each of the 2ⁿ⁻¹ remaining intervals Definition
• The subspace Γ of directions along which a series converges absolutely, and its orthogonal complement Γ^⊥ Definition
• The sum U + W of two linear subspaces and the sum ∑_i<n Uᵢ of a finite family Definition
• ⟨ a,b∣ a², b², aba⁻¹b⁻¹⟩≅(ℤ/2)×(ℤ/2) Example
• ⟨ a,b∣ aba⁻¹b⁻¹⟩≅(ℤ,+)×(ℤ,+) Example
• ⟨ a∣ aⁿ⟩≅(ℤ/n,+) for every n≥ 1 Example
• ∏_j ≥ 0 (1 - 1/(j+2)) has partial products 1/(n+1), which tend to 0, so the product does not converge in the sense used here Example
• ∫₀¹ x² = 1/3, computed from the Darboux definition with uniform partitions and the closed form ∑_k<n k² = n(n-1)(2n-1)/6 Example
• Consecutive Fibonacci numbers are coprime, and for every m ∈ ℕ the Euclidean algorithm on (Fₘ₊₃, Fₘ₊₂) takes exactly m+1 divisions, with quotient 1 in the first m of them and quotient 2 in the last Example
• Dₙ≅⟨ r,s∣ rⁿ, s², srs⁻¹r⟩ for the dihedral group Dₙ=⟨{ρ,σ}⟩leqSym(ℤ/n), n≥ 3 Example
• Every polynomial has lim_x → c p(x) = p(c), and rational functions do so away from the zeros of the denominator Example

…and 209 more results.

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 13 results over 6 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

• Mathematical induction (Wikipedia) (standard reference, not scraped)
• Set-theoretic definition of natural numbers (Wikipedia) (standard reference, not scraped)
• B. Kaya, MATH 320 Set Theory (METU lecture notes) (standard reference, not scraped)
• Peano axioms (Wikipedia) (standard reference, not scraped)