The tag has no usage guidance.

learn more… | top users | synonyms

4
votes
2answers
45 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$. I ...
1
vote
1answer
80 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
19 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
24 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)))
0
votes
0answers
33 views

simple iterate algorithm proof by induction

Suppose I have a function where it calculates which bit is larger called LargerBinary. Let's say I have an input 110111;101001, the output will be 110111 and if the input is 110110:110110, the output ...
-1
votes
2answers
80 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
53 views

Structural induction on generic list

In preparation for an exam, I've come upon the following problem. Given the constructors : ...
0
votes
1answer
59 views

Prove by induction that the running time of recursive Fibonacci is exponential

This example followed from a Fibonacci algorithm in class. The professor showed us how to compute $T(n) = T(n-1) + T(n-2) + 3$, but left this step for us to prove, so I decided to attempt to prove it! ...
0
votes
2answers
62 views
1
vote
2answers
58 views

Proving that the reversal of a language reversal is that language

I am trying to prove that with language L, (L^R) ^R =L So that the reversal of the reversal of the language is the original language L. I have proved that before with a string not language (let's ...
1
vote
2answers
63 views

Substituting two different identifiers with the same identifier in Coq - why does this work?

I'm playing around with Coq and Software Foundations and is somehow very confused by something I took for granted since forever. To prove ...
0
votes
0answers
64 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 ...
0
votes
0answers
22 views

Method of inductive statements for proving partial correctness of block-schemes

I'm trying to find an explanation and more information on a method and some example problems with solutions using that method. The method doesn't seem to translate well in english (I'm from a ...
5
votes
2answers
77 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 ...
2
votes
1answer
91 views

Sum of heights in a complete binary tree (induction)

I need to prove the following statement using induction on the number of nodes in the tree: The sum of heights of a complete binary tree is $\theta(n)$. Note: I've tried proving this using ...
0
votes
0answers
50 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 ...
2
votes
1answer
52 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? My first thought is that the algorithm introduces an $[\alpha,\beta]$ ...
0
votes
1answer
25 views

Proving equality between foldl recursive and iterative fold

Hi I have two definitions of fold. I will call them foldl which is recursive and fold$_{itr}$ which is iterative. I am looking for an algebraic proof that the two definitions are equal ideally ...
1
vote
1answer
87 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 ...
2
votes
0answers
56 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 ...
1
vote
1answer
135 views

Proof by induction concerning approximation algorithm for subset sum [closed]

Assignment question For algorithm APPROX-SUBSET-SUM, prove by induction on $i$ that for every element $y \in P_i$ that is at most the target sum $T$, there is a $z \in L_i$ such that ...
4
votes
1answer
50 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): ...
-1
votes
1answer
45 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 ...
0
votes
1answer
44 views

Complexity calculation using a recurrence relation [duplicate]

I just can't solve this problem, I'm new to reccurences. I have this recurrence $T(n)=n*T(n-1)$ $T(1)=1$ The second term will be: $T(n-1)=(n-1)*T(n-2)$ And so on. It's complexity is O(n!) but i ...
0
votes
1answer
30 views

How to read this inductive language definition?

A language $L$ is defined recursively according to the following rules: $λ ∈ L$ If $w ∈ L$, then $bw ∈ L$ and $waa ∈ L$ I am not sure if strings from this language should mix from this definition. ...
2
votes
1answer
59 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 ...
1
vote
2answers
330 views

Prove correctness of DFA ending with ab

I have the following deterministic finite automaton and I am need to prove correctness of the claim that this automata accepts $\{wab \mid w\in \{a,b\}^*\}$ I know that I need to prove by induction ...
1
vote
2answers
140 views

Solving Subproblem in Logic (first-order, propositional, pddl)

One sentence question Is there any algorithm able to prove (solve) a logic problem (first-order, propositional, pddl) by finite induction? Background I am researching Hierarchical planning solvers ...
0
votes
1answer
106 views

How do you prove two languages are equivalent using the definition of acceptance?

I need to prove that $L(f(M)) = L(M)\cup \{\varepsilon\}$ where $M$ is a DFA and $f$ is the function $f(M) := (Q\cup \{q_f\}, \Sigma, \delta', q_f, F\cup\{q_f\})$ and $q_f$ is a new state not in $Q$ ...
3
votes
2answers
95 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, ...
1
vote
1answer
42 views

Prove by Induction that $r_n$ is $O(\log_2(\log_2n))$ [duplicate]

Let the sequence $r$ be defined by: $$\begin{align*}r_{1} &= 1\\ r_n&= 1 + r_{\lfloor\sqrt{n}\rfloor}\,,\quad n\geq 2\,.\end{align*}$$ Prove by induction that $r_n$ is $O(\log_2(\log_2n))$. ...
0
votes
1answer
184 views

Structural induction over list

I want to prove that unique(reverse(L)) = reverse(unique(L)) where L is a List. List has the following constructors: ...
0
votes
1answer
68 views

Pierce's Types and Programming Languages : circular definition of terms?

In Pierce's book, on page 26-27 it is given a definition of terms for a simple language using inference rules. In the picture below it is marked by red highlighting the problematic part. What is ...
0
votes
1answer
105 views

How do I use induction to show that the language of a grammar is contained in a given set? [duplicate]

Given that I have the grammar $\qquad\displaystyle G_1 = (\{a, b, c, d\}, \{S, X, Y \}, S, \{S → XY, X → aXb, X → ab, Y → cYd, Y → cd\})$, how am I supposed to prove that $\qquad\displaystyle S(G1) ...
0
votes
0answers
28 views

Proof of the base case of Big Theta using induction [duplicate]

Here is a recursive definition for the runtime of some unspecified function. a and c are positive constants. $T(n)=a$, if $n=2$ $T(n)=2T(n/2)+cn$ if $n>2$ Use induction to prove that ...
2
votes
1answer
230 views

Proof of big theta using induction [duplicate]

Here is a recursive definition for the runtime of some unspecified function. $a$ and $c$ are positive constants. $T(n) = a$, if $n = 2$ $T(n) = 2T(n/2) + cn$ if $n > 2$ Use induction to prove ...
3
votes
1answer
57 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 ...
10
votes
4answers
254 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}} ...
1
vote
1answer
405 views

Correctness of proof by induction

Suppose a person states the following: $n^2 = (n * n), \forall n > 0$. One can check such equality by saying, via proof by induction, that: for $n := 0:\ 0^2 = (0 * 0)$; for $n := 1:\ 1^2 = (1 * ...
-1
votes
1answer
606 views

induction proof for kleene star

i posted this on mathematics stack exchange here before i realised this one existed. i am going through some past exam paper questions on regular languages for some revision, and i am having a bit of ...
2
votes
3answers
2k 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. ...
1
vote
2answers
143 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 ...
0
votes
1answer
82 views

Mathematical Induction Problem from Concrete Abstractions

This is a problem from 'Concrete Abstractions' which is available free on the web[1]. It's a book similar to SICP. The problem: Exercise 2.16 Consider the following procedure foo: ...
-1
votes
2answers
435 views

Induction proof, base case not working but induction step works? [closed]

$1+3+5+...+(2n+3)=n^2+4n$ For this series using induction proof. Base case 1,2,3,.. not working. But induction step works well. Base case is not given in question.
2
votes
2answers
228 views

How to apply the substitution method to n/2?

I recently was introduced to solving recurrence bounds by substitution but there's something i don't understand about it. In standard induction proofs you prove a base case, assume it holds for n ...
2
votes
2answers
1k 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 ...
0
votes
2answers
5k 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 ...
1
vote
0answers
128 views

How to prove the asymptotic upper bound for $T(n) = 2T(\lfloor n/2\rfloor + 17) + n$ is $O(n \log n)$? [duplicate]

I met the problem Show that the solution to $T(n) = 2T(\lfloor n/2\rfloor + 17) + n$ is $O(n \log n)$ while reading Introduction to Algorithm. It's a question about the substitution method for ...
1
vote
0answers
76 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 ...
1
vote
0answers
788 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 ...