Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [induction]

Questions about mathematical induction and inductive proofs.

Filter by
Sorted by
Tagged with
21 votes
1 answer
18k views

How do I write a proof using induction on the length of the input string?

In my Computing Theory course, a lot of our problems involve using induction on the length of the input string to prove statements about finite automata. I understand mathematical induction, however ...
tcdowney's user avatar
  • 313
20 votes
3 answers
2k views

Is path induction constructive?

I'm reading through the HoTT book and I have a hard time with path induction. When I look at the type in the section 1.12.1: $$\text{ind}_{=_A}:\prod_{C:\prod\limits_{x,y:A}(x=_Ay)\to \mathcal{U}} \...
Kostya's user avatar
  • 473
14 votes
1 answer
2k views

What is induction-induction?

What is induction-induction? The resources I found are: the HoTT book, at the end of chapter 5.7. nLab's article a paper called Inductive-inductive definitions this blog post also mentions inductive-...
盛安安's user avatar
  • 944
12 votes
3 answers
13k views

Trying to understand this Quicksort Correctness proof

This proof is a proof by induction, and goes as follows: P(n) is the assertion that "Quicksort correctly sorts every input array of length n." Base case: every input array of length 1 is already ...
FrostyStraw's user avatar
11 votes
12 answers
10k views

Why are mathematical proofs so hard?

I am an electrical engineer and trying to make a transition into machine learning. I read in multiple articles that I have to learn data structures and algorithms, before this I have to learn about ...
user28324's user avatar
  • 239
11 votes
3 answers
889 views

Do "inductively" and "recursively" have very similar meanings?

Do "inductively" and "recursively" mean very similar? For example, if there is an algorithm that determines a n-dim vector by determine its first k+1 components based on its first k components having ...
Tim's user avatar
  • 4,925
9 votes
1 answer
1k views

Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$

Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$. The book from which this example is, falsely claims that $T(n) = O(n)$ by guessing $T(n) \leq cn$ and then arguing $\qquad \...
Saurabh's user avatar
  • 919
7 votes
1 answer
5k views

Prove correctness of recursive multiplication algorithm

I'm in a first year discrete math course and we started algorithms. I created a recursive algorithm to multiply two numbers together: ...
user12243's user avatar
7 votes
3 answers
500 views

Proving property of a term using Induction

This is one of the example lemma that has been proved in TAPL book which I'm unable to grasp. The objective is to prove |Consts(t)| <= size(t) where ...
Sibi's user avatar
  • 171
6 votes
4 answers
590 views

How does one know what statements in Coq require Induction?

I was trying to learn Coq using the famous book Software Foundations. In it I found the following: ...
Charlie Parker's user avatar
6 votes
2 answers
566 views

Help with proof involving weighted full binary tree

Given a full binary tree, $T$ (each node is either a leaf or possesses exactly two children), with $n$ leaf nodes: $v_1,v_2,...,v_n$, and weights associated with the leaf nodes: $w_1,w_2,...,w_n$, the ...
so.very.tired's user avatar
5 votes
4 answers
17k views

How to find whether a grammar's language is finite or infinite?

I have this context-free grammar and I want to find out whether its language is finite or infinite. ...
Dana's user avatar
  • 355
5 votes
3 answers
16k views

Language of balanced parentheses; Biconditional proof about parentheses

Let L be language of balanced parentheses. (a) Prove If there are equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'s, then w is in L. (b) Prove If w is in L, then ...
user678392's user avatar
5 votes
2 answers
2k views

Finding nested intervals efficiently

The intervals are represented as two numbers, e.g. $(4.3, 5.6)$. The intervals are unique. If for $(x,y)$ and $(u,v)$, $x≤u$ and $v≤y$, $(u,v)$ is nested in $(x,y)$ How do I find out which ...
The Unfun Cat's user avatar
5 votes
1 answer
262 views

Proof by induction over rules for mutually recursive relations

Consider the (big-step) semantics of a language ($a, e$ terms, $v$ values), defined by two mutually recursive relations, $\downarrow$ and $\Downarrow$, given by a set of rule-schemata (simplified): $\...
choeger's user avatar
  • 610
5 votes
1 answer
1k views

How to prove that the pre-order tree traversal algorithm terminates?

I see structural induction the usual way for proving an algorithm's termination property, but it's not that easy to prove by means of induction on a tree algorithm. Now I am struggling on proving that ...
WIZARDELF's user avatar
  • 301
5 votes
0 answers
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: ...
Joey Eremondi's user avatar
4 votes
2 answers
17k views

Prove correctness of recursive Fibonacci algorithm, using proof by induction

I'm studying for the computer science GRE, and as an exercise I need to provide a recursive algorithm to compute Fibonacci numbers and show its correctness by mathematical induction. Here is my ...
winston smith's user avatar
4 votes
2 answers
490 views

Lambda Calculus inductive substitution definition

I'm reading Lambda-Calculus and Combinators: An Introduction, and there's the following definition of $\lambda$-substitution: $FV(P)$ stands for the set containing all free-variables from $P$. ...
Aristu's user avatar
  • 1,483
4 votes
2 answers
177 views

Is structural induction on terms applicable when a function is involved?

Assume an evaluation-relation on terms $t \Downarrow v$. If I want to prove correctness of a function $\phi$ w.r.t. evaluation, I have to show that the following implication always holds: $$\frac{\...
choeger's user avatar
  • 610
4 votes
1 answer
99 views

Which inductive schemes can encode the following Agda definition?

Which induction schemes (e.g. induction-recursion by Dybjer and Setzer, "Irish" induction-recursion by McBride or induction-induction by Forsberg and Setzer or perhaps some simpler ones) allow one to ...
Primary Key's user avatar
4 votes
1 answer
973 views

Induction to prove equivalence of a recursive and iterative algorithm for Towers of Hanoi

Using induction how do you prove that two algorithm implementations, one recursive and the other iterative, of the Towers of Hanoi perform identical move operations? The implementations are as follows....
gunnnnii's user avatar
4 votes
1 answer
570 views

How to use structural induction to prove law on lists

I want to prove that the following equation holds using structural induction on (finite) lists ...
futtetennista's user avatar
4 votes
2 answers
536 views

How to pick a good structural induction hypothesis

(Full disclosure: homework question) Let $M = (Q, \Sigma, q_0, A, \delta)$ be a finite automaton. The extended transition function $\delta^*$ is defined as follows: $\forall q \in Q$ $\delta^*(q, \...
itsjareds's user avatar
4 votes
1 answer
333 views

Proof on tree size using Isabelle

I'm trying to learn a little bit about Isabelle and proofs in general, and it's uses in Programming Language Theory. I'm following a book, "Concrete Semantics with Isabelle/HOL". I'm still in the ...
Amaral's user avatar
  • 41
4 votes
1 answer
91 views

Proving that $(A \cup B)^* = A^*(BA^*)^*$

I would like to prove that $(A \cup B)^* = A^*(BA^*)^*$, where * means the Kleene star. I would like to use induction to prove this equality but I do not how to proceed and how is the best way to set ...
abarbosa's user avatar
4 votes
0 answers
228 views

PL: How can I prove the type of something using "Inversion for Typing"?

I'm currently going through this book about programming languages, and in section 4.2, Lemma 4.2 it says this: Lemma 4.2 (Inversion for Typing). Suppose that $\Gamma \vdash e : \tau$. If $e = \texttt{...
Reed Oei's user avatar
  • 203
3 votes
2 answers
294 views

Why does the denotational semantics for a while loop have a existence quantifier?

I was going through these notes and they have the following operator on partial functions: $$ \mathcal F^{k}(\bot)(\sigma) = \left\{ \begin{array}{ll} \alpha( [\![s]\!]\sigma ) & [\![b]\!]\...
Charlie Parker's user avatar
3 votes
2 answers
234 views

Is this graph Hamiltonian?

My case is a directed graph with $n$ nodes with $(n-1)^2+1$ edges. I have done the following till now. We know that the maximum number of edges for a directed graph $K_n$ on $n$ nodes is $n(n-1)$ ...
Amal Sailendran's user avatar
3 votes
2 answers
2k views

Proof of correctness of algorithms (induction)

I am reading Algorithm's Design Manual by S.Skiena and I have a hard time understanding and proving the correctness of algorithms. I should use proof by induction and when we talk about summations and ...
Martin Spasov's user avatar
3 votes
1 answer
273 views

When can the coinduction hypothesis be used?

We can use the induction hypothesis when we are proving a property for a structure that is well-ordered. I am aware that there is a proof for this. When it comes to coinduction, I'm confused. One of ...
Russell's user avatar
  • 153
3 votes
1 answer
45 views

Invariance Textbook Problem: Clarification Needed

I am currently reading Michael Soltys' Analysis of Algorithms (2nd Edition), and Problem 1.13 of the subsection titled Invariance reads: Let $n$ be an odd number, and suppose that we have the set $\{...
Ziad Ismaili Alaoui's user avatar
3 votes
2 answers
752 views

CLRS Rod Cutting Inductive proof

I'd like to preface this question by saying that it is not a homework question. However, it is a question regarding the course material. In the rod-cutting example an equation is presented to ...
Kurt's user avatar
  • 131
3 votes
1 answer
555 views

Induction proof of alpha-beta search

Is there a functional specification of alpha-beta search that makes it easy to prove by induction that the algorithm works?
wlad's user avatar
  • 479
3 votes
1 answer
211 views

Proving laws of take and drop functions using structural induction on lists

I'm trying to prove the following laws using structural induction on (finite) lists: ...
futtetennista's user avatar
3 votes
1 answer
173 views

Using induction to prove transition states are the same

Suppose that you have a DFA $M=\left(S,\Sigma,s_0,\delta,{s_f}\right)$ with $s_f\neq s_0$. Suppose further that, for all $a\in\Sigma$, $\delta\left(s_0,a\right)=\delta\left(s_f,a\right)$. Show that ...
Cain's user avatar
  • 63
3 votes
0 answers
83 views

Formalize the proof of theorem 2.4 in Harper's PFPL

In Harper's Practical Foundations for Programming Languages, page 19, rule (2.9) defines the $sum$ function inductively. $$ \frac{b:nat}{sum(zero;b;b)}\tag{rule 2.9a} $$ $$ \frac{sum(a;b;c)}{sum(succ(...
gingerologist's user avatar
3 votes
0 answers
100 views

Induction pitfalls with O notation and recursion

I read the following in CLRS 3rd Ed: I'm not sure I understand exactly how to avoid this pitfall. How would one know that the $\mathcal{O}$ notation in this case grows with $n$ and is thus not ...
Amelio Vazquez-Reina's user avatar
2 votes
2 answers
638 views

Induction rules for reflexive, transitive closure

I'm trying to solve an exercise on inductive definitions, the premiss is: Let $\to$ be a relation on $A$ and $\to^*$ its reflexive, transitive closure, which is defined by following two rules: $a \...
mike's user avatar
  • 175
2 votes
1 answer
617 views

Can we prove mathematical induction statements in Lisp?

My previous question Can we prove that $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ using a computer program? has a problem that it tries to cover too much ground. Here is a related question motivated by ...
john mangual's user avatar
  • 1,951
2 votes
2 answers
138 views

Proving that there is no solution to the PCP problem using induction

I'm studying for the Algorithms and Computability course. I have encountered a problem that I cannot solve and cannot find any materials to help me solve it. It's the following PCP problem: We have ...
Miszka's user avatar
  • 23
2 votes
2 answers
137 views

Greedy algorithm-maximal minimum average of n pairs

Lets assume $2n $ gifts such that each gift $i$ has price $a_i$ The goal is to find a partition of the gifts into $n$ pairs such that each pair $P_i=\left(a_{i_{0}},a_{i_{1}}\right)$ has maximal ...
Danny Blozrov's user avatar
2 votes
1 answer
90 views

Deriving recursive definition from function specification

Given this function specification, where name xs is bound to a list, # denotes its cardinality and ...
F. Zer's user avatar
  • 125
2 votes
1 answer
335 views

Induction on typing derivation in refinement types system

From the text Principles of Type Refinement page 14: The author introduces in definition 2.2.7 the rule: $$ \dfrac{\Pi \vdash t : R \qquad R \le S}{\Pi \vdash t : S} $$ and gives the following ...
user1868607's user avatar
  • 2,194
2 votes
2 answers
225 views

Structural induction on generic list

In preparation for an exam, I've come upon the following problem. Given the constructors : ...
user43389's user avatar
  • 260
2 votes
2 answers
439 views

Rule induction principles in Harper's PFPL

I have a few small questions about section 2.4 ("Rule induction") in Practical Foundations for Programming Languages (p. 19). (1) In the rule induction principles for ...
Fixnum's user avatar
  • 71
2 votes
1 answer
110 views

Bounding the height of a tree in a variant of disjoint set union

Consider a variant of link-by-size implementation of the Union–Find data structure, in which trees will be linked by the logarithm of the size. Let $\ell_i$ = $⌊\log_2|T_i|⌋$ and, when merging $T_i$ ...
SVMteamsTool's user avatar
2 votes
1 answer
239 views

Prove by induction $T(n) = T(\lfloor\frac{n}{2}\rfloor)+n^2 \in \Theta (\log_2 n)$

Text of the problem: Solve the following recurrence equation and prove it by applying the principle of induction: $T(n) = \begin{cases} 3, \ n \le 2 \\ T(\lfloor\frac{n}{2}\rfloor)+n^2, \ n \ge 3 \...
Loris Simonetti's user avatar
2 votes
3 answers
234 views

solving a problem with induction

The original question is the following prove that $2·\sum_{i=0}^{n-1} 3^{i} = 3^n-1$ for all n $\geq$ 1 I know that I have to prove by induction and have successfully done the base case, my IH is ...
MaximeB's user avatar
  • 33
2 votes
1 answer
2k views

Is Loop Invariant Proof a form of Induction?

As far as I see, what computer scientists refer to as loop invariant proofs are exact replicas of induction proof. Is it true? Can I state that loop invariant proof implies an induction? Is there a ...
Ninja Bug's user avatar
  • 249