Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [induction]

Questions about mathematical induction and inductive proofs.

178 questions
Filter by
Sorted by
Tagged with
1 vote
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
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 ...
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
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
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, ...
46 views

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 ...
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 ...
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 ∨ ...
83 views

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
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 ...
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
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
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 ...
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
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 ...
16 views

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]...
239 views

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?
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$? ...
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
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)$ ...