Questions tagged [induction]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
41 views

Is this reduction process always commutative?

There was a question posted on this website earlier today by a new Account "Nick". He asked, ...
Snared's user avatar
  • 109
1 vote
0 answers
152 views

Prove that every group $G$ with $p^n$ ($n\ge4$) elements and center with $p$ elements has an abelian subgroup of order $p^3$ [closed]

Prove that every group $G$ with $p^n$ ($n\ge4$) elements and center with $p$ elements has an abelian subgroup of order $p^3$ I'm new in this forum so I hope I haven't made any mistake. I have to ...
Francesco Bradanini's user avatar
6 votes
1 answer
403 views

A summation involving fraction of binomial coefficients

I need to prove the following statement. Let $ n, g, m, a ,t$ be integers. Prove that the following statement is true for all $ n \geq g(1+2m)+1 $, $ g\geq 2t $, $ m\geq t $, $ 0\leq a <t $, and $ ...
Arda Aydin's user avatar
2 votes
1 answer
93 views

Summation of rows of a matrix P^k is decreasing with the power k

I have the following $(n+1)\times (n+1)$ matrix $$P = \begin{bmatrix} f(0) & g(0) & 0 & 0 & 0 & \dots & 0\\ f(1) & 0 & g(1) & 0 & 0 & \dots & 0\\ f(2) &...
K. Bountrogiannis's user avatar
2 votes
1 answer
166 views

Terminology associated with mathematical induction

In "Number: The Language of Science" (1930), Tobias Dantzig refers to what we call the base case of mathematical induction as "the induction step" (and refers to what we call the ...
James Propp's user avatar
  • 19.4k
49 votes
7 answers
7k views

Zorn's lemma: old friend or historical relic?

It is often said that instead of proving a great theorem a mathematician's fondest dream is to prove a great lemma. Something like Kőnig's tree lemma, or Yoneda's lemma, or really anything from this ...
Pace Nielsen's user avatar
2 votes
0 answers
237 views

Largest eigenvalue of a Laplacian matrix to lower bound the prime counting function?

Let $L_n$ be the Laplacian matrix of the undirected graph $G_n = (V_n, E_n)$ (which is defined here: Why is this bipartite graph a partial cube, if it is? ) with sorted spectrum: $$\lambda_1 (G_n) \ge ...
mathoverflowUser's user avatar
1 vote
0 answers
124 views

What does "sup" mean in the context of a w type? [closed]

Like the constructor for a W type is called "sup" but I don't know what that expands to. Is it super? maybe supremum? Or is it just an arbitrary name, like dynamic programming?
Glubs's user avatar
  • 109
5 votes
0 answers
218 views

Induction for quantum group

I am confused about a claim in the article Representation of quantum algebras by Henning Haahr Andersen, Patrick Polo and Wen Kexin. I probably misunderstood a definition, but I found two claims about ...
Nicolas Hemelsoet's user avatar
1 vote
1 answer
124 views

Mathematical induction and the counting function on $\mathbb{Z}_p^2$

Let $\mathbb{Z}_p$ be a finite field of order $p$ and $\mathbb{Z}_p^2$ be a $2$-dimensional vector space over $\mathbb{Z}_p$. We consider the distance $\lVert \cdot \rVert:\mathbb{Z}_p^2\to \mathbb{Z}...
RFZ's user avatar
  • 298
0 votes
1 answer
123 views

Nicely motivated papers or book chapters on the formula for the sum of the $k$-th powers of the first natural numbers [closed]

Do you know of a text where I can find a nicely motivated proof of the formula for $1^{k}+2^{k}+\cdots+n^{k}$? At the very beginning of page 68 of Professor H. S. Wilf's generatingfunctionology, one ...
Jamai-Con's user avatar
15 votes
2 answers
2k views

How to structure a proof by induction in a maths research paper?

I am 16 years old at the time of writing (so I have no supervisors to seek advice from) and I have written a mathematics research paper, which I plan on submitting to a journal for publication. I ...
A-Level Student's user avatar
-1 votes
1 answer
58 views

Seek help to formalize an argument to positiveness of function defined inductively by integral [closed]

I have on domain $[0,\infty)$ a known and positive function $f(x)$ and two unknown functions $g(x), h(x)$ that start positive when $x=0$. I also know that if $h(x)$ is positive, then $g(x)$ is also ...
Quiet_waters's user avatar
2 votes
0 answers
114 views

Can you define inductive data types over categories other than Set?

Can you define inductive data types over categories other than $\mathbb{Set}$? What does it look like? How about for a specific example like the category of monoids? If you were clever could you write ...
Molly Stewart-Gallus's user avatar
17 votes
0 answers
405 views

Is the Frog game solvable in the root of a full binary tree?

This is a cross-post from math.stackexchange.com$^{[1]}$, since the bounty there didn't lead to any new insights. For reference, The Frog game is the generalization of the Frog Jumping (see it on ...
Vepir's user avatar
  • 591
1 vote
0 answers
352 views

Generalizations of classical tiling problem

A classic problem using an inductive construction is to show that the $2^n \times 2^n$-square, with a missing corner, can be tiled with L-triominoes. The proof goes like this: It is true for $n=1$, ...
Per Alexandersson's user avatar
6 votes
2 answers
168 views

Limit of alternated row and column normalizations

Let $E_0$ be a matrix with non-negative entries. Given $E_n$, we apply the following two operations in sequence to produce $E_{n+1}$. A. Divide every entry by the sum of all entries in its column (...
Axel Carré's user avatar
3 votes
1 answer
162 views

Models of arithmetical theory R + induction in which successor is not injective

Consider the arithmetical theory sometimes denoted by $\mathsf{R}$. The non-logical vocabulary of $\mathsf{R}$ consists of '$0$', '$S$', '$+$' and '$\times$'. The axioms of this theory are all true ...
Thomas Schindler's user avatar
1 vote
1 answer
178 views

An iterative argument involving $f(n + 1) - f(n) $

I am working with an argument involving an inequality of the form: $$ f(n + 1) \leq f(n) + C (f(n))^{1 - \frac{1}{\gamma}} \qquad(\ast)$$ where $f$ is a positive function, $\gamma > 0$ and $C >...
Marcelo Ng's user avatar
2 votes
2 answers
428 views

(Types of) induction on infinite chains

This question may be trivial, or overly optimistic. I do not know (but I guess the latter...). I am a group theorist by trade, and the set-up I describe cropped up in something I want to prove. So ...
NotDominicRaab's user avatar
5 votes
1 answer
330 views

Why restrict to $\Sigma_1^0$ formulas in $RCA_0$ induction?

I recently asked this question over on math.se, warmly welcomed by crickets. I hope it's appropriate here. I'm reading Stillwell's Reverse Mathematics, and the induction axiom was just introduced. ...
luqui's user avatar
  • 585
9 votes
1 answer
2k views

Is There an Induction-Free Proof of the 'Be The Leader' Lemma?

This lemma is used in the context of online convex optimisation. It is sometimes called the 'Be the Leader Lemma'. Lemma: Suppose $f_1,f_2,\ldots,f_N$ are real valued functions with the same ...
Daron's user avatar
  • 1,761
6 votes
2 answers
684 views

Cases where multiple induction steps are provably required

I am looking for references for theorems of the form: 1) Any proof of theorem $X$ requires $n$ applications of induction axioms and especially 2) Any proof of theorem $X$ requires $n$ nested ...
manzana's user avatar
  • 335
0 votes
2 answers
204 views

Are Regularity schema and $\in$-induction schema equivalent in intuitionistic logic?

In posting "Does Regularity schema imply $\in$-induction when added to first order Zermelo set theor?" the answer was that they are equivalent in classical first order logic with membership "$\in$". ...
Zuhair Al-Johar's user avatar
1 vote
2 answers
283 views

Does Regularity schema imply $\in$-induction when added to first order Zermelo set theory?

That $\in$-induction fails to be a theorem schema of first order Zermelo + Foundation (see here), then it appears that it is more eligible to replace axiom of Regularity (Foundation) by a Regularity ...
Zuhair Al-Johar's user avatar
7 votes
1 answer
484 views

Is $\in$-induction provable in first order Zermelo set theory?

Are there models of first order Zermelo set theory (axiomatized by: Extensionaity, Foundation, empty set, pairing, set union, power, Separation, infinity) in which $\in$-induction fail? I asked this ...
Zuhair Al-Johar's user avatar
3 votes
2 answers
556 views

How to estimate a recursive inequality with an upper bound

The below is a simplification of part of a proof I'm working on, in numerical analysis. It is similar to a paper that I studied some months ago, for which I got some advice here on MathOverflow. I ...
Cogicero's user avatar
  • 167
7 votes
1 answer
235 views

Independent/Easy fraction of sentences over PA

Let $S(n)$ be the set of all sentences over PA of length at most $n$ (counting the quantifier symbols, boolean connectives, arithmetic operations and constants, and counting each variable as length $1$...
user21820's user avatar
  • 2,734
-2 votes
1 answer
382 views

Towers of induced functions

Suppose $\mathbb{X}$ and $\mathbb{Y}$ are classes, and $f:\mathbb{X}\rightarrow\mathbb{Y}$. It seems like pretty standard course to consider an 'induced function' $f:\mathcal{P}\mathbb{X}\rightarrow\...
Alec Rhea's user avatar
  • 8,947
1 vote
0 answers
147 views

Proving the existence of a sequence with recursive growth constraints

Fix $0 < c < 1/3$. Show that there exists a strictly increasing sequence $a_k > 0$, a sequence $b_k \geq 0$, and an infinite set $K \subseteq \mathbb{Z}_{>0}$ such that \begin{align}\...
ThomasMBerndt's user avatar
5 votes
4 answers
691 views

Mathematical induction vis-a-vis primes

One of the most used proof-techniques is mathematical induction, and one of the oldest subjects is the study of prime numbers. Thanks to Euclid, we can consider the primes as a infinite monotone ...
6 votes
1 answer
578 views

Inductive Definitions in Category Theory

I'm trying to pin down a notion of inductive definability in category-theoretic terms. The sorts of inductively defined sets (and classes) I'm most interested in are those that admit of induction and ...
Patrick's user avatar
  • 63
3 votes
0 answers
537 views

When must one strengthen one's induction hypothesis?

My questions are about the phenomenon that in order to prove a fact $\forall x \phi(x)$ by induction, sometimes straightforward induction "does not work" and instead one "must" use a "stronger" ...
Anders Lundstedt's user avatar
23 votes
5 answers
3k views

Is Cauchy induction used for proofs other than for AM–GM?

The proof by Cauchy induction of the arithmetic/geometric-mean inequality is well known. I am looking for a further theorem whose proof is much neater by this method than otherwise.
John Bentin's user avatar
  • 2,427
4 votes
1 answer
343 views

Affine analog of the theory of sheets

In the study of adjoint orbits in a complex semi-simple lie algebra, there is a well known object known as a "sheet". These are the irreducible components of the union of orbits of the same dimension. ...
Aswin's user avatar
  • 1,063
4 votes
0 answers
123 views

Problem with a proof in Wellfounded trees in categories

I'm reading the paper Wellfounded trees in categories by Moerdijk and Palmgren. I'm having trouble understanding the proof of Theorem 7.2 (page 216), i.e. that in $\mathbf{ML}_{< \omega} \mathbf{W}$...
Luca Bressan's user avatar
1 vote
0 answers
72 views

A curious example envolving moment's convergence

Let $\{X_n\}$ be a random variable sequence and $X\sim N(0,\sigma)$. In general, the convergence $E(X_n^k) \stackrel{n}{\longrightarrow}E(X^k)$ doesn't implie that $E(X_n^{k+1}) \stackrel{n}{\...
S. W. M's user avatar
  • 67
3 votes
0 answers
508 views

Two (strictly related) proofs by induction of inequalities

This is a question I originally asked on MSE, receiving no answer, even with a bounty (which expired) on it. Therefore I am crosslinking in order to prevent duplication of effort: see here for the ...
Vincenzo Oliva's user avatar
19 votes
8 answers
2k views

Unconventional types of induction

Induction is one of the most common tools is mathematics, and everybody knows the ordinary induction and the strong induction. However, in some proofs induction is applied in an unexpected and elegant ...
3 votes
2 answers
743 views

notable inductive proofs relating to fractals

what are notable/ prominent inductive proofs relating to fractals? the motivation for this question is: fractals are very difficult mathematical objects to work with, and many problems/questions ...
vzn's user avatar
  • 529
3 votes
2 answers
973 views

Neither Even Nor Odd Natural Numbers

Modular arithmetic (MA) has the same axioms as first order Peano arithmetic (PA) except $\forall x(Sx \neq 0)$ is replaced with $\exists x(Sx=0)$. In Even XOR Odd Infinities? I asked if this statement ...
Russell Easterly's user avatar
36 votes
3 answers
4k views

the following inequality is true,but I can't prove it

The inequality is \begin{equation*} \sum_{k=1}^{2d}\left(1-\frac{1}{2d+2-k}\right)\frac{d^k}{k!}>e^d\left(1-\frac{1}{d}\right) \end{equation*} for all integer $d\geq 1$. I use computer to verify ...
useag's user avatar
  • 363
9 votes
1 answer
930 views

ERA, PRA, PA, transfinite induction and equivalences

I'm quite sure I don't understand very well the links between proof theoretical ordinals of theories, the axioms of transfinite induction and the objects a theory can prove to exist. For instance I'm ...
Primitive Recursive Fab's user avatar
1 vote
3 answers
3k views

Why Does Induction Prove Multiplication is Commutative?

Andrew Boucher's General Arithmetic (GA2) is a weak sub-theory of second order Peano Axioms (PA2). GA has second order induction and a single successor axiom: $$\forall x \forall y \forall z\bigr((Sx=...
Russell Easterly's user avatar
7 votes
4 answers
1k views

Examples of "exotic" induction

Next week I am going to teach two lessons on induction to very motivated students from high schools. At some point I would like to talk about ordered sets, well-ordered sets, and mention the fact that ...
8 votes
2 answers
2k views

Homotopy Transfer Theorem for Differential Graded Associative Algebras

As in Algebra+Homotopy=Operad by Bruno Vallette, let $A$ with multiplication $\nu$ be a differential graded associative algebra equipped with degree +1 map $h$ and let $H$ be a chain complex such that ...
Daniel Briggs's user avatar
1 vote
0 answers
159 views

Coinduction and corestriction are quasi-inverse equivalences for comodules?

I'm reading http://arxiv.org/abs/math/0310337. There the following statement is given without proof: Let $k$ be a field. Let $C$ be a counitary coaugmented coalgebra, i.e. there is $\eta: C\to k$ ...
Julian Kuelshammer's user avatar
0 votes
1 answer
851 views

Maximum sum of 3 consecutive numbers in a permutation [closed]

Given that $X = \{0, 1, 2, ..., 7, 8, 9\}$, and $P$ is a permutation on $X$. Let $M(P)$ be the maximum sum of 3 consecutive elements. For example, if $P = (0, 2, 4, 1, 5, 7, 9, 3, 8, 6)$, then $M(P)$ ...
somethingsomething's user avatar
8 votes
2 answers
1k views

Order statistics (e.g., minimum) of infinite collection of chi-square variates?

Hi everyone, This is my first time here, so please let me know if I can clarify my question in any way (incl. formatting, tags, etc.). (And hopefully I can edit later!) I tried to find references, ...
David M Kaplan's user avatar
32 votes
11 answers
10k views

Is PA consistent? do we know it?

1) (By Goedel's) One can not prove, in PA, a formula that can be interpreted to express the consistency of PA. (Hopefully I said it right. Specialists correct me, please). 2) There are proofs (...