Questions tagged [induction]

Questions about mathematical induction and inductive proofs.

Filter by
Sorted by
Tagged with
0
votes
0answers
21 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 ...
0
votes
0answers
53 views

Induction proof given recurrence of algorithm

I am having trouble starting this proof and wanted some clarification. Here are the details given: ...
0
votes
0answers
55 views

Using induction prove that a K-SAT problem is NP-Complete

Using induction on k, how do I prove that the K-SAT problem is NP-complete? On wikipedia, it describes the Cook-Levin theorem to prove that K-SAT is NPC by reducting the K-SAT problem to a circuit-...
0
votes
0answers
31 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 ...
5
votes
0answers
39 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: ...
0
votes
0answers
15 views

Is this proof of the map fusion law correct?

I am reading Functional Programming in Scala, where I have been asked to prove the map fusion law. Since Scala is what I am familiar with, I am using as my notation a kind of pseudo-Scala. Here is ...
1
vote
0answers
43 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 \\...
2
votes
1answer
23 views

Proving that a property is k-inductive with an SMT solver (parametric resettable counter)

I'm following the slides at https://homepage.cs.uiowa.edu/~tinelli/talks/FT-11.pdf where Tinelli explains how k-induction works in the context of SMT based model checking. A parametric and resettable ...
0
votes
0answers
21 views

Structural induction a particular case of (co)induction rule of an inductive predicate

What is the relation between the principle of induction on terms: ...
1
vote
1answer
61 views

Proving a DFA recognizes a language using induction

The following DFA recognizes the language containing either the substring $101$ or $010$. I need to prove this by using induction. So far, I have managed to split each state up was follows: q0: ...
0
votes
0answers
37 views

Proof that this sorting algorithm sorts the input

I'm given this "sorting" algorithm and now I'm supposed to prove, that if given an array of integers of length $n$, sort(A,0,n-1) will sort it. ...
0
votes
1answer
64 views

Recursive definition for the length of a string?

I found a couple of answers online but I don't quite understand why the answer is right: The length of a string is: If a string has no characters, then its length is 0. Otherwise, the length of the ...
0
votes
0answers
59 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 = ...
0
votes
0answers
34 views

dfa subtract multiple of 3 [duplicate]

Define a function 𝑑𝑖𝑓𝑓 ∈{0,1}→ℤ so: for everything w ∈{0,1}, diff w = # of 1's in w- # of 0's in w. Thus: 𝑑𝑖𝑓𝑓 𝜀=0; 𝑑𝑖𝑓𝑓 0=−1; 𝑑𝑖𝑓𝑓 0=−1; Let 𝐿 = {𝑤∈ {0,1} * | 𝑑𝑖𝑓𝑓 𝑤 = 3𝑚 ...
0
votes
2answers
231 views

prove by induction that the complete recursion tree for computing the nth Fibonacci number has n leaves

I have referenced this similar question: Prove correctness of recursive Fibonacci algorithm, using proof by induction *Edit: my professor had a significant typo in this assignment, I have attempted ...
1
vote
0answers
62 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
535 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
269 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
95 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
121 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\\ ...
4
votes
4answers
164 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
61 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
205 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
325 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 ...
1
vote
0answers
33 views
0
votes
1answer
37 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
75 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
80 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
75 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
37 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
62 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
90 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 ...
1
vote
1answer
266 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
121 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
110 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
143 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 ...
1
vote
0answers
46 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
54 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 ...
2
votes
0answers
16 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
56 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
323 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
37 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
107 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
359 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
385 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
134 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
111 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
283 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
119 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
324 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 ...