Questions tagged [induction]
The induction tag has no usage guidance.
56
questions
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 ...
- 18.1k
43
votes
4
answers
4k
views
A principle of mathematical induction for partially ordered sets with infima?
Recently I learned that there is a useful analogue of mathematical induction over $\mathbb{R}$ (more precisely, over intervals of the form $[a,\infty)$ or $[a,b]$). It turns out that this is an old ...
- 64.8k
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 ...
- 363
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 (...
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.
- 2,427
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 ...
17
votes
0
answers
407
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 ...
- 591
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 ...
- 253
12
votes
6
answers
28k
views
Induction vs. Strong Induction
Is there ever a practical difference between the notions induction and strong induction?
Edit: More to the point, does anything change if we take strong induction rather than induction in the Peano ...
11
votes
3
answers
2k
views
Easier induction proofs by changing the parameter
When performing induction on say a graph $G=(V,E)$, one has many choices for the induction parameter (e.g. $|V|, |E|$, or $|V|+|E|$). Often, it does not matter what choice one makes because the proof ...
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 ...
- 1,761
9
votes
1
answer
936
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 ...
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 ...
- 986
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, ...
- 101
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 ...
7
votes
1
answer
485
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 ...
- 9,256
7
votes
1
answer
236
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$...
- 2,733
6
votes
2
answers
689
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 ...
- 335
6
votes
2
answers
170
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 (...
- 163
6
votes
1
answer
588
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 ...
- 63
6
votes
1
answer
409
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 $ ...
- 63
6
votes
1
answer
853
views
Symmetric Proof that Product is Well-Founded
This is a fairly minor, technical question, but I'll toss it out in case someone has a good idea on it.
Suppose $(X,<_X)$ and $(Y,<_Y)$ are well-founded orderings (not necessarily linearly ...
- 7,125
5
votes
1
answer
332
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.
...
- 585
5
votes
4
answers
696
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 ...
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 ...
4
votes
6
answers
5k
views
Proofs by induction [closed]
Background
I'm interested in the issue of "explanatory" mathematical proofs and would like to try to find out what intuitions mathematicians have about induction, because there seems to be some ...
- 315
4
votes
1
answer
477
views
For which classes of functions this inverse function formula gives a closed form expression?
Lets consider this method of finding inverse function:
$$f^{-1}(x) = \sum_{k=0}^\infty A_k(x) \frac{(x-f(x))^k}{k!}$$
where coefficients $A_k(x)$ recursively defined as
$$\begin{cases} A_0(x)=x \\ ...
- 9,312
4
votes
1
answer
345
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. ...
- 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}$...
- 181
3
votes
2
answers
2k
views
How to restore the original formula from a binomial-like expansion?
I encountered with a recursive formula of the following kind:
$$A(0,x)=1$$
$$A(n,x)= \sum _{j=0}^{n-1} \binom{n-1}{j} A(n-j-1,x) \sum _{k=0}^{x-1} A(j,k)$$
The sum terms can be re-arranged so to ...
- 9,312
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 ...
3
votes
2
answers
558
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 ...
- 167
3
votes
2
answers
748
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 ...
- 529
3
votes
2
answers
975
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 ...
- 687
3
votes
0
answers
539
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" ...
- 155
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 ...
2
votes
2
answers
432
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 ...
2
votes
1
answer
94
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) &...
2
votes
1
answer
171
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 ...
- 19.4k
2
votes
0
answers
238
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 ...
- 2,462
2
votes
0
answers
116
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 ...
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=...
- 687
1
vote
2
answers
284
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 ...
- 9,256
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}...
- 298
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 >...
- 245
1
vote
0
answers
178
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 ...
1
vote
0
answers
125
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?
- 109
1
vote
0
answers
361
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$, ...
- 15.6k
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}\...
- 161
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}{\...
- 67