Questions tagged [induction]

Questions about mathematical induction and inductive proofs.

Filter by
Sorted by
Tagged with
3 votes
1 answer
36 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 $\{...
Ziad Ismaili Alaoui's user avatar
0 votes
1 answer
49 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, ...
petrit.vidishiqi's user avatar
0 votes
2 answers
51 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 ...
Mason Rashford's user avatar
1 vote
2 answers
164 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 ...
Mason Rashford's user avatar
0 votes
0 answers
109 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 ...
Mohamed Hendy's user avatar
0 votes
3 answers
104 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 ...
newlogic's user avatar
  • 165
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 ...
newlogic's user avatar
  • 165
0 votes
2 answers
50 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, ...
not_castillo's user avatar
1 vote
0 answers
45 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 $\...
alim's user avatar
  • 994
0 votes
0 answers
31 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 ...
blu's user avatar
  • 1
0 votes
0 answers
85 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 ...
hcentenaro's user avatar
0 votes
0 answers
35 views

Trouble understanding inductive proof of Lomuto's partitioning algorithm

I'm doing a review of sorting algorithms and trying to self-learn how to prove them as well. The foundation of the quicksort proof is intuitive enough if I'm assuming that the recursion holds - but ...
blu's user avatar
  • 1
0 votes
0 answers
133 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 ∨ ...
Jxb's user avatar
  • 318
0 votes
0 answers
74 views

Proving that the polish notation has unique readability

I am familiar with the polish notation when it comes to algorithmically reading phrases, but I am having a hard time proving the following exercise: K is a function so that 1) $K(*)$ is an integer if ...
Tita's user avatar
  • 225
3 votes
0 answers
82 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(...
gingerologist's user avatar
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 ...
coderodde's user avatar
0 votes
0 answers
77 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,...
ErroR's user avatar
  • 1,904
2 votes
2 answers
127 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 ...
Miszka's user avatar
  • 23
0 votes
1 answer
36 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 ...
infinicky's user avatar
0 votes
2 answers
57 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: $...
gorilla_glue's user avatar
-1 votes
1 answer
269 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 ...
Hjm's user avatar
  • 47
2 votes
2 answers
131 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 ...
Danny Blozrov's user avatar
0 votes
2 answers
141 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 ...
MiddleEasternPrince's user avatar
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) \...
V_head's user avatar
  • 33
0 votes
0 answers
110 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 ...
learner_b's user avatar
-1 votes
1 answer
85 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, $\...
Jamāl's user avatar
  • 179
0 votes
1 answer
52 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: ...
darkshadowx's user avatar
1 vote
1 answer
62 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 ...
maya cohen's user avatar
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 $...
Adamat's user avatar
  • 1
2 votes
1 answer
107 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$ ...
SVMteamsTool's user avatar
1 vote
1 answer
56 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 ...
Lance's user avatar
  • 2,193
0 votes
1 answer
59 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. ...
meguli's user avatar
  • 293
0 votes
0 answers
15 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 ...
Jason Durant's user avatar
2 votes
1 answer
224 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 \...
Loris Simonetti's user avatar
1 vote
2 answers
330 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, ...
Slim Shady's user avatar
0 votes
1 answer
48 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?
Ali Adin's user avatar
0 votes
1 answer
66 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 ...
Curious Scientist's user avatar
1 vote
1 answer
25 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 ...
Philipp's user avatar
  • 61
2 votes
1 answer
208 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 $...
Michal Dvořák's user avatar
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)$ ...
Amal Sailendran's user avatar
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\...
MathCurious's user avatar
1 vote
1 answer
206 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 ...
daniel's user avatar
  • 11
1 vote
1 answer
11 views

Inductive sequence of words in a biprefix code

Let $X = X_1 \cup X_2$ a code on an alphabet $A$, with $X_1$ a biprefix code and $X_2$ a uniform code, with $m(X_1) < m(X_2)$, i.e. the maximal length of the first is strictly lower than the second....
Cat's user avatar
  • 115
1 vote
1 answer
1k 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, ...
user avatar
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 ...
PsychoKitten's user avatar
0 votes
3 answers
245 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]...
Demokles's user avatar
0 votes
1 answer
44 views

Doing induction on recurrences correctly

I have $$T(n)=T(n-1)+n^{2}$$ And I know, by drawing the recursion tree that this is $\Theta (n^{3})$ However, if I try claiming that it's $O(n^{2})$ through induction: $$T(n)\le c(n-1)^{2}+n^{2}\le cn^...
Essam's user avatar
  • 155
0 votes
2 answers
193 views

Prove by induction that a recurrence has solution $T(n)=\Theta(n^2 \log_{3}n)$

Prove by induction that $T(n)=\Theta(n^2 \log_{3}n)$ where $$T(n)= \begin{cases} 1 & \mbox{if } n=1,\\ 9T(\lceil n/3 \rceil)+n^2 & \mbox{otherwise.} \end{cases}$$ The base case for $n=1$ seems ...
Frank's user avatar
  • 147
1 vote
1 answer
22 views

Proof the number of expected node in a binary using mathematical induction

The following algorithm constructs a binary tree. ...
Www's user avatar
  • 73
0 votes
2 answers
89 views

Failing to solve a recurrence by induction

My question is strongly related to the one asked here: How do I show T(n) = 2T(n-1) + k is O(2^n)? $$T(n)=2T(n-1)+1$$ Going with the steps, I reached the point where: $$c*2^{n}\geq c*2^{n}+1$$ which ...
Essam's user avatar
  • 155