# Questions tagged [induction]

Questions about mathematical induction and inductive proofs.

36 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
61 views

### Rules for consistency with mutual inductive families?

I'm trying to use a proof assistant to define a type and a relation that are mutually dependent on each other: ...
• 29.8k
229 views

180 views

I found out an exercise where you have to prove the correctness of the following CFG: Let $L=\{ 0^i 1^j|2i \leq j \leq 3i \}\:$ and $\: G: S\rightarrow 0S11 | 0S111| \epsilon$ claim: Every string $w ... 0 votes 0 answers 169 views ### Inductive proof that$n^2 + bn + d$is$O(n^2)$using definition of big O Given that$T(n) = n^2 + bn + d$then it's$O(n^2)$if I can prove that:$O(n^2) = \{T(n): \text{there exist positive constants } c, n_0 \text{ such that } \forall n \geq n_0, 0 \leq T(n) \leq cn^2 \}... • 13 0 votes 0 answers 241 views ### How does the induction proof work in this example? Refer to answer 1.1 of this file: http://www.dei.unipd.it/~geppo/AA/DOCS/NPC.pdf From my understanding and this thread, https://math.stackexchange.com/a/928412, we need 3 steps for that proof. ... • 445 0 votes 0 answers 48 views ### How would one prove that the following scheme definition is an ordered stream of integers How would one prove that the following scheme definition is an ordered stream of integers (define integers (cons-stream 1 (add-streams ones integers))) • 173 0 votes 0 answers 655 views ### Describe the language generated by a given context free grammar I had an exercise: Describe the language generated by the following given context free grammar and prove it by induction. \begin{align} S &\to SA \mid \epsilon \\ A &\to aS \mid bA \... • 121 -1 votes 1 answer 87 views ### How to resolve the clash between definition of Big O notation and Inductive Hypothesis when proving running time by substitution method? Suppose you have to prove the solution to the following recurrence by Induction, T(n)= \begin{cases} \Theta(1), & n=1 \\ 2 T(\lfloor n/2 \rfloor)+\Theta(n), & n>1 \end{cases}$Here,$\...
• 179
How I can explain this. Consider the following automaton, $A$. Prove using the method of induction that every word/string $w\in L(A)$ contains an odd number(length) of $1$'s. Show that there are ...