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

Questions tagged [induction]

Questions about mathematical induction and inductive proofs.

Filter by
Sorted by
Tagged with
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 ...
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 ...
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, ...
1 vote
1 answer
2k views

Prove correctness of in-order tree traversal subroutine

I'm trying to prove that in-order tree traversal prints the keys in sorted order. It's shown here, but what I want is to prove correctness using ordinary induction. Claim: For any n-node subtree, ...
1 vote
1 answer
61 views

Solving Recurrence Relations with induction

We got the following tasks in our Higher Algorithm class, to repeat our proof techniques from class: Find asymptotic upper bounds (as sharp as possible) for $T(n)$ in each of the following cases, ...
3 votes
1 answer
46 views

Invariance Textbook Problem: Clarification Needed

I am currently reading Michael Soltys' Analysis of Algorithms (2nd Edition), and Problem 1.13 of the subsection titled Invariance reads: Let $n$ be an odd number, and suppose that we have the set $\{...
4 votes
1 answer
91 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
2 answers
52 views

Prove $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})=\Theta(n\log^2{n})$ using induction

Please first take a brief look at my previous question. Here I want to do something similar but for $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})$. I know the answer is $T(n)=\Theta(n\log^2{n})$ and I want ...
1 vote
2 answers
181 views

Prove $T(n)=10T(\frac{n}{3})+n\sqrt{n}=\Theta(n^{\lg_3{10}})$ using induction

We have this recurrence: $$T(n)=10T(\frac{n}{3})+n\sqrt{n}.$$ We can solve it using Master Theorem and say it is $\Theta(n^{\log_3{10}})$. I want to prove it using induction but I don't know the ...
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 ...
0 votes
3 answers
138 views

When to do proof by structural induction Vs defining a recursive function?

I'm trying to isolate the key differences between induction and recursion so that I am able to know when to use one over the other. From my understanding, both can be used to prove properties about ...
0 votes
2 answers
37 views

Can proofs by induction be achieved by defining a recursive function between two recursive objects?

I have two types of objects, X and Y, each are recursive structures, and contain different structures sets of tuples containing sets.. etc. The number of elements in X and Y are is the same. I need to ...
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 $\...
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 ...
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 ...
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 ∨ ...
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(...
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 ...
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,...
2 votes
2 answers
139 views

Proving that there is no solution to the PCP problem using induction

I'm studying for the Algorithms and Computability course. I have encountered a problem that I cannot solve and cannot find any materials to help me solve it. It's the following PCP problem: We have ...
0 votes
1 answer
37 views

Logic for Computer Science - How to define msort, merge and split functions inductively?

In "Modelling Computing Systems: Mathematics for Computer Science", I came across a logic exercise to inductively define a merge sort function 'mergeSort', with a hint to first define ...
0 votes
2 answers
59 views

Dropping terms in proving the runtime for a recurrence?

I am trying to learn how to prove the runtime of a recurrence relation, particularly through induction. I was looking at this lecture PDF, and on the first page, the author writes this: Recurrence: $...
-1 votes
1 answer
316 views

EXACT INDSET is DP-complete

The class DP is defined as the set of languages L for which there are two languages $L1 \in NP$ , $L2 \in coNP$ such that $L = L1 \cap L2$. (Do not confuse DP with $NP \cap coNP$, which may seem ...
2 votes
2 answers
137 views

Greedy algorithm-maximal minimum average of n pairs

Lets assume $2n $ gifts such that each gift $i$ has price $a_i$ The goal is to find a partition of the gifts into $n$ pairs such that each pair $P_i=\left(a_{i_{0}},a_{i_{1}}\right)$ has maximal ...
0 votes
2 answers
177 views

Proof: CFG has balanced parentheses

I'm currently enrolled to a CS course about programming languages and we learned about structural induction. In a question from our home assignments we need to proof that the following CFG has ...
1 vote
1 answer
60 views

0<i => 0 < i + j proof?

If we have the natural numbers defined as: Plus the following: $pred \space \_\_<\_\_ \space: Nat \times Nat$ $\forall i,j:Nat$ $0<suc(j)$ $\neg(i<0)$ $suc(i) < suc(j) \...
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 ...
-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, $\...
0 votes
1 answer
63 views

Recursive function - proof by induction

Let $\Sigma$ denote an alphabet and $[ \Sigma ]$ set of lists. I've encountered the following function: $f([])=[]$ (empty list) $f([x])=[x]$, for $x \in \Sigma$ $f(x:L)=f(L)$, for $x \in \Sigma$ and $...
1 vote
1 answer
45 views

Induction on recursive formula

I have this recursive formula $$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)+O\left(n\right)+2O\left(1\right) \ \ \ ➜ \ \ \ T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)$$ $$T\...
0 votes
1 answer
53 views

Structural induction proof for reverse(push(as, bs)) = push(reverse(bs), reverse(as))

I need to prove: reverse(push(as,bs)) = push(reverse(bs), reverse(as)) where: ...
1 vote
1 answer
64 views

Language generated by $S \to aAb|Sb$, $A \to aAb|ab$

Let $G = (\{A,S\}, \{a,b\}, S, P\}$ be the grammar with the following productions: \begin{align} & S \to aAb | Sb \\ & A \to aAb | ab \end{align} What is the language $L(G)$ generated by the ...
2 votes
1 answer
110 views

Bounding the height of a tree in a variant of disjoint set union

Consider a variant of link-by-size implementation of the Union–Find data structure, in which trees will be linked by the logarithm of the size. Let $\ell_i$ = $⌊\log_2|T_i|⌋$ and, when merging $T_i$ ...
1 vote
1 answer
1k views

Every AVL tree can be colored to be a red-black tree

I want to prove any AVL tree can be turnt into a red-black tree by coloring nodes appropriately. Let $h$ be the height of a subtree of an AVL tree. It is given that such a coloring is constrained by ...
1 vote
1 answer
66 views

What does type theory as a theory of inductive definitions mean?

Unfortunately copy/paste doesn't work for this paper Inductive Definitions and Type Theory, but here is a snippet. The paper begins by stating: The first sentence of the second paragraph says type ...
0 votes
1 answer
64 views

Proving loop invariant for a possibly nonterminating while loop

I started studying through Aho, Ullman - Foundations of Computer Science as a free time exercise. In the second chapter about loop invariants and inductive proofs, there is a starred exercise. ...
1 vote
1 answer
163 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
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 ...
7 votes
3 answers
500 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 ...
20 votes
3 answers
2k 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}} \...
0 votes
3 answers
261 views

What makes an algorithm greedy?

I have a simple graph $G = (V,E)$ and each vertex has a range $[a,b]$. Every two vertices are connected only if $[a_1, b_1]$ and $[a_2, b_2]$ have a common subrange. Each range of vertex is rV1 = [0,5]...
2 votes
1 answer
239 views

Prove by induction $T(n) = T(\lfloor\frac{n}{2}\rfloor)+n^2 \in \Theta (\log_2 n)$

Text of the problem: Solve the following recurrence equation and prove it by applying the principle of induction: $T(n) = \begin{cases} 3, \ n \le 2 \\ T(\lfloor\frac{n}{2}\rfloor)+n^2, \ n \ge 3 \...
3 votes
2 answers
752 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 ...
1 vote
2 answers
365 views

Show that for a singly-connected graph the number of edges $E$ must be equal to the number of vertices minus $1$, $E=V-1$

I am reading "Bayesian Reasoning and Machine Learning By David Barber". I am not completely sure how to do question 19 on page 23: Show that for a connected graph that is singly-connected, ...
2 votes
1 answer
228 views

Prove that up to isomorphism there are exactly two graphs s.t. there at most two vertices with same degree

I've proven the following: For each $n\in\mathbb{N},n\geq 2$ there exists a graph on $n$ vertices such that all degrees are distinct except two. Formally for each $n$ there exists a graph on vertices $...
0 votes
1 answer
49 views

How can I use induction for proving termination of a string rewriting system?

If we have a string rewriting system within the alphabet $\{X,Y\}^*$ and the rule $XY\to YX$. How can we prove by induction that on every string input the system terminates?
0 votes
1 answer
544 views

How can I prove the correctness of this exponentiation algorithm using induction?

I have the following algorithm. How could I prove it using induction that for every $n\ge 0$, Exp(n)${}= 2 ^ n$? ...
0 votes
1 answer
67 views

Prove that the following algorithm is $\Theta(n^3)$ by induction

I have the following algorithm runtime: $T(1) = b $ for some positive constant. Otherwise, $T(n)=8T(\frac n 2) + 100n^2$ I am trying to prove that it is $\Theta(n^3)$ by induction. I proved that it is ...
1 vote
1 answer
26 views

Substitution Method to Solve Recurrences

One approach to solve recurrences is the so called substitution method. While practicing I encountered some recurrences, where non integer arguments can occur, e.g. T(n) = 2*T(n/2) + n, if n is not a ...
3 votes
2 answers
234 views

Is this graph Hamiltonian?

My case is a directed graph with $n$ nodes with $(n-1)^2+1$ edges. I have done the following till now. We know that the maximum number of edges for a directed graph $K_n$ on $n$ nodes is $n(n-1)$ ...