Questions tagged [induction]

The tag has no usage guidance.

10 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
248 views

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

This is a cross-post from math.stackexchange.com$^{}$, 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 ...
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 ...
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}$...
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" ...
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 ...
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 ...
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$, ...
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}\...