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

Questions tagged [induction]

Questions about mathematical induction and inductive proofs.

37 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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
0 answers
229 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
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
0 answers
50 views

Is this a correct way of using structural induction to prove type uniqueness?

I was reading the book "Types and Programming Languages" by Benjamin C. Pierce, paying attention to proofs so I could learn proof techniques. In the parts discussing the simply typed $\...
alim's user avatar
  • 1,014
2 votes
0 answers
19 views

Induction / (machine learning) of Resource Grammars for Grammatical Framework?

Grammatical Framework is based in Abstract Categorial Grammars. It is known that Combinatory Categorial Grammars have grammar induction/learning capabilities see e.g. https://link.springer.com/article/...
TomR's user avatar
  • 1,401
2 votes
0 answers
52 views

Structural induction in non-local program transformation

Assume a functional language and a specialization operation (pulling out sub-expressions): let f x y = (h 23 x) + (g 42 y) becomes ...
choeger's user avatar
  • 610
2 votes
0 answers
69 views

Self referential data

Can anyone show me step by step how to do a proof on self referential structures. For example, this example is in scala ...
Abdul Rahman's user avatar
2 votes
0 answers
4k views

Insertion sort Proof by Induction

I am reading Algorithm design manual by Skiena. It gives proof of Insertion sort by Induction. I am giving the proof described in the below. Consider the correctness of insertion sort, which we ...
amitabha's user avatar
  • 121
1 vote
0 answers
72 views

Finding the total work of an array list expansion effort

Suppose we are given an array-based list data structure. Suppose that its initial capacity is $m > 0.$ When appending an element to the end of the list, if the list is full, we extend its capacity ...
coderodde's user avatar
1 vote
1 answer
221 views

Prove the following claim on Hamilton Path?

I am trying to prove the following claim: Given DAG graph, there is Hamilton path iff the following algorithm returns true: Do topologic sorting. Move on the graph's vertices one by one (from low to ...
daniel's user avatar
  • 11
1 vote
1 answer
105 views

Using inductive hypothesis on recurrence relation?

I have a recurrence relation as follows $$T(n) = 2T(\lfloor n/2\rfloor) + n\log(n)$$ Using the induction hypothesis how do I obtain a relation $T(n)\leq E$ such that $E$ contains neither $T$ nor floor ...
Jon Anderson's user avatar
1 vote
0 answers
49 views

Hanoi towers recursive expression for EVERY algorithm

What the recursive algorithm for moving $n$ disks says, is: If $n > 1$, move $n-1$ discs from A to B. Move the $n$th disk from A to C. If $n > 1$, move $n-1$ discs from B to C. Let $T_n$ be ...
entechnic's user avatar
  • 143
1 vote
0 answers
273 views

How to prove a recursive's function Big-Theta without using repeated substitution, master theorem, or having the closed form?

I have a function defined: $V(j, k)$ where $j, k \in \mathbb{N}$ and $t > 0 \in \mathbb{N}$ and $1 \leq q \leq j - 1$. Note $\mathbb{N}$ includes $0$. $V(j, k) = \begin{cases} tj & k \leq 2 \\...
user12055579's user avatar
1 vote
0 answers
163 views

Inductive proof on Quicksort with Explicit Stacking

Prove by induction that if Quicksort with Explicit Stacking is modified so that the end-points of the larger sublist are stacked, and the other sublist is sorted first, then the maximum stack size is $...
Ferrari_M's user avatar
1 vote
0 answers
325 views

How to prove that the predecessor of each node in Dijkstra form a tree?

Prove that the array prev[.] computed by Dijkstra’s algorithm, the edges (v, prev[v]) for all v ∈ V , form a tree In order to prove this I used induction. Lemma :...
user94729's user avatar
1 vote
0 answers
148 views

Program equivalence with Structural induction

I recently attended my first lecture on structural induction and the professor stated that structural induction can be used to to prove that two programming languages are equivalent. I am new to ...
anil keshav's user avatar
1 vote
0 answers
95 views

Proving that a BST with N>=1 nodes will have log(N+1) levels

I am trying to prove by induction the following theorem: Use Induction to prove the following fact: for every integer, $N\ge 1$ , a BST with $N$ nodes must have at least $\log( N + 1)$ levels. I've ...
elobeto's user avatar
  • 11
0 votes
0 answers
204 views

Proof of The Optimality Of Greedy Algorithm for The Interval Scheduling Problem

I have this proof for the optimality of the greedy algorithm for the interval scheduling problem in my algorithms class, but I'm struggling to understand it fully, especially starting from the second ...
Mohamed Hendy's user avatar
0 votes
2 answers
58 views

Proving T(n) = 3T(n/9) + n^1/2 using induction

I'm confused on how to prove the below using induction: T(n) = 3T(n/9) + √n I have been given the base case T(1) = 1. I know using the master theorem that the time complexity is O(√n log n). However, ...
not_castillo's user avatar
0 votes
0 answers
35 views

Consolidating my proof for the merge step of mergesort

I've been spending time strengthening my ability to conduct inductive proofs and made one for the mergesort algorithm - specifically the merge part, as the entirety of the algorithm is comparatively ...
blu's user avatar
  • 1
0 votes
0 answers
129 views

Prove that BFS computes the shortest path from one vertex to another

I read in Algorithms in C by Sedgewick that we can easily prove by induction that breadth-first search algorithm computes the shortest path from one vertex to another (unweighted graphs or weighted ...
hcentenaro's user avatar
0 votes
0 answers
140 views

Why weakening rule doesn't increase the size of resolution refutation?

I am studying the complexity of SAT resolution refutation. There is a useful tool named weakening rule The weakening rule: B -->B ∨ C says that from a clause B we can derive the weaker clause B ∨ ...
Jxb's user avatar
  • 318
0 votes
0 answers
78 views

Proving correctness of a particular algorithm

Suppose there is an array $A[1..n]$.$A$ contains a permutation of $\{1,2,3,\dots,n\}$. We run the following algorithm $m$ times to sort $A$: for each odd index of $A$ from left to right ,respectively,...
ErroR's user avatar
  • 1,942
0 votes
0 answers
112 views

Prove that the total number of parenthesizations of n matrices is Ω(4^n/n^3/2)

Is it possible to prove the total number of parenthesizations of n matrices is Ω(4^n/n^3/2) using the Induction Method? Recurrence formula from CLRS book When n = 1, the sequence consists of just one ...
learner_b's user avatar
0 votes
0 answers
16 views

Bounding Summation - Geometric Series

When proving the bound on a summation in the Analysis of Algorithms when proving the bound also applies to $n+1$ the following inequalities are derived by the induction hypothesis: $$\sum^{n}_{k=0}3^k ...
Jason Durant's user avatar
0 votes
0 answers
39 views

Is my understanding of strictness correct in this proof of a `foldl` rule?

Exercise G in Chapter 6 of Richard Bird's Thinking Functionally with Haskell asks the reader to prove foldl f e . concat = foldl (foldl f) e given the rule ...
neurozero's user avatar
  • 101
0 votes
0 answers
152 views

Prove grade-school multiplication algorithm applied to binary numbers

I want to prove that the basic multiplication algorithm is correct when applied to binary numbers. I try to follow the steps described here and here but didn't succeed. The basic implementation ...
sabotero's user avatar
  • 101
0 votes
0 answers
160 views

proving DFA stuck

This DFA fulfills: Define a function $diff: \{0,1\}^*\to\Bbb Z$, for $w \in\{0,1\}^*$, $diff(w)=($# of 1's in $w)- ($# of 0's in $w$). Thus, $diff(\epsilon)=0$; $diff(0)=−1$; $diff(1)=1$. Let $L = ...
Ives Rodriguez's user avatar
0 votes
0 answers
180 views

When proof by induction on length string is not possible?

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 ...
NoOne's user avatar
  • 1
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 \}$...
john's user avatar
  • 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. ...
aste123's user avatar
  • 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)))
Abdul Rahman's user avatar
0 votes
0 answers
654 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 \...
chamburger's user avatar
-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, $\...
Jamāl's user avatar
  • 179
-1 votes
2 answers
590 views

proof using induction of automaton

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 ...
autstam's user avatar
-1 votes
1 answer
719 views

Proving correctness of a recursive algorithm using induction

For the program mean(A,n) if n = 1 then return A[n] else return A[n]/n+mean(A,n-1)*(n-1)/n end Show that if the recursive call to ...
Nati0n's user avatar
  • 1