Questions tagged [induction]

The tag has no usage guidance.

10 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
12
votes
0answers
248 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 ...
5
votes
0answers
194 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
0answers
119 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}$...
3
votes
0answers
462 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" ...
3
votes
0answers
505 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
0answers
80 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
0answers
240 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$, ...
1
vote
0answers
136 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}\...
1
vote
0answers
65 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}{\...
1
vote
0answers
143 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$ ...