Questions tagged [induction]
Questions about mathematical induction and inductive proofs.
180
questions
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 $\{...
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,
...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 $\...
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 ...
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 ...
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 ...
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 ∨ ...
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 ...
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(...
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
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,...
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 ...
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 ...
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: $...
-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 ...
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 ...
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 ...
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
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 ...
-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, $\...
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:
...
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 ...
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 $...
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$ ...
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 ...
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.
...
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 ...
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 \...
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, ...
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?
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 ...
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 ...
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 $...
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)$ ...
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\...
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 ...
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....
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, ...
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 ...
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]...
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^...
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 ...
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.
...
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 ...