Stack Exchange Network

Stack Exchange network consists of 175 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

Questions tagged [induction]

Questions about mathematical induction and inductive proofs.

0
votes
0answers
44 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 $...
0
votes
1answer
202 views

Is my proof of my greedy algorithm to find subsequence correct?

Credit to KleinBerg and Taros Book Some of your friends have gotten into the burgeoning field of time-series data mining, in which one looks for patterns in sequences of events that occur over time. ...
2
votes
2answers
123 views

Iterative Fibonacci algorithm correctness proof, finding loop invariants

The algorithm take in an integer $n$ and outputs the $n$th number in the Fibonacci sequence ($F_n$). The sequence starts with $F_0$. I am trying to prove the correctness assuming valid input: ...
0
votes
0answers
42 views

Correctness proof: induction on sequence of steps, need a stronger claim?

Im trying to prove the correctness of the construction proposed in this site answer: a two stack PDA that simulates a Turing Machine. By "correctness" i mean to prove more or less formally that we can ...
1
vote
1answer
58 views

Induction on strings (words)

Given is an alphabet $\Sigma = \{ 0, 1, 2 \}$ and a function quer to calculate the cross sum of a word. $quer : \Sigma^*\to \Bbb N$ with: $$quer(w)=\begin{cases} 0, &\text{when } w=\epsilon\\ ...
3
votes
3answers
85 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: ...
0
votes
0answers
32 views

How do I show that an iterative solution to Tower of Hanoi performs the same exact steps as a recursive solution? [duplicate]

So given the typical recursive solution to the Tower of Hanoi problem wherein you reduce the n-disk tower to two instances of an (n-1)-disk tower i.e move (n-1) disks from start to auxiliary. move ...
2
votes
1answer
81 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....
1
vote
2answers
146 views

Proof of QuickSort algorithm correctness

Recently I’ve studied QuickSort and understood its general idea. Basically, we do the following: Pick an element from the array (no matter which one and how in this context) Rearrange elements in ...
0
votes
0answers
17 views
0
votes
1answer
32 views

Is this a valid induction proof example ?

Learning induction proof now, found a "simple" example, which is a bit confusing to me (not sure if it is a valid example). If so, why the IH( suppose a root of rank k has at least $2^k$ vertices in ...
1
vote
0answers
48 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
67 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]\!]\...
3
votes
0answers
54 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
32 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
51 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
67 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
86 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
68 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
69 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
115 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
234 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
43 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 ...
1
vote
1answer
45 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
11 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
46 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 \}$...
1
vote
3answers
283 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
85 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
301 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
308 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
104 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
101 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
248 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
106 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
303 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
149 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 ...
2
votes
2answers
995 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
251 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
80 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
103 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
1k 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
48 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 ...
10
votes
3answers
6k 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
321 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
51 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
854 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
114 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 ...