Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

0
votes
0answers
54 views

Inductive Proof of Sorting Algorithm

Problem Consider the pseudocode for the sort algorithm below, which takes as input an unsorted array $A$ of $n$ integers with no duplicates. ...
1
vote
0answers
41 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 :...
3
votes
2answers
64 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]\!]\...
0
votes
0answers
24 views

Proof by induction on “Equivalence of NFA, ε-NFA”

I would appreciate if anyone could help me out with the portion of the proof where I have to construct an NFA from an $\epsilon$-NFA. I do know that doing it otherwise is easy. I am new to the concept ...
3
votes
0answers
36 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 = \...
-1
votes
1answer
31 views

How to prove even with structural induction, for expression

E::= zero|two|expression + expression|expression*expression, E element of expression how do i prove E to be even. I have no clue on how to go about tackling this.
3
votes
1answer
48 views

How to prove that a string is made up of subsequences occurring some arbitrary number of times using concatenation?

How to prove that a string, s is made up of n > 1 subsequences occurring some arbitrary number of times using concatenation ...
2
votes
1answer
48 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 ...
0
votes
1answer
34 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 ...
2
votes
1answer
35 views

Proving time-complexity analysis for merge-sort-like algorihtm

I have this algorithm, which is exactly like merge-sort, but instead of halving the array each recursion, it actually splits it into $1/4$ and $3/4$ parts. Other then that, it does exactly the same ...
0
votes
2answers
50 views

Proving the correctness of a square summing algorithm

int sumHelper(int n, int a) { if (n==0) return a; else return sumHelper(n-1, a + n*n); } int sumSqr(int n) { return sumHelper(n, 0); } I am supposed ...
0
votes
0answers
95 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 ...
0
votes
0answers
197 views

Proof by induction of recurrence relation of dynamic programming

I am currently solving the problem using dynamic programming: Description: saying that there are inputs in 2D-array (width = 8, height = 6): ...
0
votes
0answers
10 views

Solving a recurrence relation by substitution [duplicate]

I need to show that solution of $T(n)=T(n-1) + n$ is $O(n^2)$ by substitution method. Can somone explain how can i procede? and maybe show the steps to get the solution. Thanks in advance.
1
vote
0answers
40 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 ...
0
votes
0answers
52 views

Proving correctness for computing spans with a stack

Was researching about computing stock spans with a Stack and how the running time of it is $O(n)$. However, how does one prove correctness on it? ...
1
vote
1answer
40 views

Prove that the number of full nodes plus one is qual to the number of leaves in a nonempty binary tree

I'm trying to write an induction statement to prove a full node in a tree but I have no idea how to do that. I've always been terrible when it comes to logic. Where do I even start with this? I know ...
1
vote
0answers
8 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/...
0
votes
0answers
40 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 \}$...
0
votes
0answers
713 views

AVL Tree: Proving minimum number of nodes

I'm practicing for my final exam, and I'm a bit confused. Here's the question: Let M(h) be the minimum number of nodes in an AVL tree of height h. In such a tree, it can be shown that $M(h) = M(h-...
1
vote
3answers
231 views

Prove correctness for computing the nth Fibonacci number for the pseudo code

How do we prove the correctness of this pseudo code by induction? ...
1
vote
1answer
35 views

Complex property of sparse horner polynomials by induction

I'm following this article to do a formal proof on elliptic curve cryptography. My question here addresses only a property "easily proved by induction". Definitions (the important part is the ...
0
votes
1answer
73 views

Can you give an inductive definition to define the length of a list L?

Having trouble understanding what it means to define something inductively in the following context. Can you give an inductive to define the length of a list L? a. The total number of items in ...
1
vote
2answers
278 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 \...
4
votes
1answer
272 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 ...
0
votes
1answer
92 views

Where I can find example how prove red black tree?

I need prove that any red-black tree with at least two elements obtained through the insertion algorithm has at least one red node. For this, I need use Induction. I don't understand how apply ...
3
votes
1answer
98 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: ...
2
votes
1answer
219 views

Prove the equivalence between a CFG and a Context free language

I have to prove that the language $L=\{a^ib^j:2i=3j+1\}$ and the CFG G with the following rewrite rules: $S\rightarrow a^2Tb$ $T\rightarrow a^3Tb^2 |\epsilon$ are equivalent to each other. I'm ...
1
vote
2answers
101 views

Using Induction to prove that $n^3log^4n=O(n^4)$

I need to prove the following asymptotic relation for the purpose of cacluating a recurrence relation: $$n^3log^4n=O(n^4)$$ I tried and failed to do it with induction, which, if possible using basic ...
6
votes
3answers
292 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 ...
1
vote
2answers
60 views

Can you apply the induction hypothesis to its outcome?

Assume a well-founded relation $<$ over a set $S$ and a property $P$ on $S$ such that: $P$ holds for all minimal elements of $S$. For every $b \in P$ and $a < b$ we have: if $P(a)$ then there ...
0
votes
1answer
109 views

Proof by mathematical induction

Before we start, my textbook declares lgn as base two. I only have one question, how did log2 become n (both highlighted in yellow in the picture)? Is it because log2 = 1, which is too small to even ...
1
vote
1answer
837 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 ...
2
votes
2answers
199 views

How to prove with induction [duplicate]

So far I have learned how to write proofs by induction and it went fine until I got this recursive problem, which I'm not quite sure how to begin and how to prove that with induction. ...
2
votes
2answers
77 views

Prove correctess of recurrence result by mathematical induction

I have the following recurrence relation which I already solved using repeated substitution. $T(n) = \begin{Bmatrix} 1 & if & n = 1\\ 4T(\frac{n}2) + n & if & n >= 2 \end{Bmatrix} ...
4
votes
2answers
98 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{\...
9
votes
1answer
907 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-...
2
votes
0answers
46 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 ...
9
votes
3answers
5k 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 ...
1
vote
1answer
279 views

Show that $T(n) = 2T(\lfloor n/2\rfloor) + n$ is $\Omega(n\log n)$ using substitution

I have to solve this using the substitution method. Floor functions cannot be skipped. IH: Assume that $T(k) \geq ck\log(k) $ for all $k \leq n$, where c is a constant. IS: Must prove $T(k) \geq ...
1
vote
2answers
47 views

How do I approach inductive design problems with no information or context given?

As a starting point for our course in Artificial Intelligence, we are being taught induction. We received a number of homework assignments where we have to show our inductive approach for a given ...
1
vote
2answers
739 views

How to prove that the reversal of the concatenation of two strings is the concatenation of the reversals?

Given languages $L_1$ and $L_2$, how do we prove that $$(L_1L_2)^{\mathrm{rev}} = (L_2^{\mathrm{rev}})(L_1^{\mathrm{rev}})\,,$$ where ${}^{\mathrm{rev}}$ denotes reversal? I think using mathematical ...
1
vote
0answers
111 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 ...
0
votes
0answers
172 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. ...
4
votes
2answers
258 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$. ...
1
vote
1answer
143 views

How to use the concept of loop invariant to reduce errors in loops?

Most of time while writing loops I usually write wrong boundary conditions(eg: wrong outcome) or my assumptions about loop terminations are wrong(eg: infinitely running loop). Here is an small example ...
0
votes
1answer
50 views

Why do I need a base case for n=3 when solving a d&c recurrence?

I was reading CLRS' book on how to use the substitution method to solve recurrences, where they have the following example: $T(n) = 2T(\lfloor{\frac{n}{2}}\rfloor) + n$ where $T(1) = 1$ They assume ...
0
votes
0answers
35 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)))
-1
votes
2answers
178 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 ...
1
vote
2answers
113 views

Structural induction on generic list

In preparation for an exam, I've come upon the following problem. Given the constructors : ...