Questions tagged [induction]

Questions about mathematical induction and inductive proofs.

Filter by
Sorted by
Tagged with
1
vote
1answer
55 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 ...
19
votes
3answers
1k 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
3answers
144 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
1answer
292 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, ...
2
votes
1answer
55 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
1answer
259 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 ...
3
votes
2answers
561 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
1answer
54 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
1answer
22 views

Induction on recursive formula

Okay so I have this recursive formula $T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)+O\left(n\right)+2*O\left(1\right) \ \ \ ➜ \ \ \ T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\...
1
vote
2answers
68 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
1answer
69 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
1answer
39 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
1answer
125 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
1answer
42 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
1answer
18 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
2answers
210 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)$ ...
0
votes
0answers
39 views

A problem in proving with induction

According to asked question in this post. Suppose $T(n,k)=T(n-1,k-1)+T(n-1,k)+1$, now let $C(n,k)=T(n,k)+1$. As a result $C(n,k)=C(n-1,k-1)+C(n-1,k)$. I want to prove $C(n,k)=2\binom{n}{k}$, now on ...
1
vote
1answer
9 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....
0
votes
2answers
94 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 ...
0
votes
1answer
37 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^...
1
vote
1answer
19 views
0
votes
2answers
80 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 ...
11
votes
12answers
8k views

Why are mathematical proofs so hard?

I am an electrical engineer and trying to make a transition into machine learning. I read in multiple articles that I have to learn data structures and algorithms, before this I have to learn about ...
1
vote
1answer
41 views

How to show a function is primitive recursive by induction?

I know, loosely speaking, if we can define a function $f$ in term of \begin{align} &f(0,\vec{x})=g(\vec{x})\\ &f(n+1,\vec{x})=h(f(n),n,\vec{x}) \end{align} where functions $g,h$ are primitive ...
1
vote
1answer
36 views

Proving that grammar generates language with multi variable inequalities

I am struggling with trying to come up with the inductive proofs to prove that the following grammar is equal to $ L = \{0^m1^n | m \leq 2n, n \leq 2m \}$ The grammar is $ S → A \:|\: B $ $ A → 00A1 \:...
1
vote
1answer
33 views

Determining which recursive term is bigger if they share the same definition

We are given a recursive definition: $a_1 = x,\\a_2=y, \\a_n= c_1a_{n-1}+c_2a_{n-2} \text{ for }n\ge3 $ where $x,y,c_1,c_2,n$ are natural numbers we are to prove that $a_n \le c_3^n$ for all n The ...
0
votes
0answers
29 views

Is my understanding of strictness correct in this proof of a `foldl` rule?

Exercise G in Chapter 6 of Richard Bird's Thinking Functionally with Haskell asks the reader to prove foldl f e . concat = foldl (foldl f) e given the rule ...
1
vote
1answer
84 views

on coq: Why is the proof complete after proving only for one induction when we have more than one variable?

So I'm learning coq. And I came across the proof for associativity in addition forall (a b c : nat) Appearntly when we do ...
0
votes
1answer
68 views

Proving building a balanced BST out of sorted array is $\Theta(n)$

I'm having hard time proving building a balanced BST out of sorted array is $\Theta(n)$ I got the following formula: $$T(n)=2T(\frac{n}{2})+\Theta(1)$$ I tried to prove it by induction but got stuck ...
1
vote
1answer
49 views

Prove by induction that the recurrence form of bubble sort is $\Omega(n^2)$

The recurrence form of bubble sort is $T(n)=T(n-1)+ n- 1$ How can I prove by induction that this is $\Omega(n^2)$? I'm stuck with $T(n+1) \geq cn^2 + n = n(cn+1)$
0
votes
1answer
199 views

Given a tournament with $2^n$ vertices, show that there is a sub-tournament with at least $n + 1$ vertices that is acyclic

So a tournament is just a complete directed graph, I believe. I'm having trouble proving this problem. I know it is induction however. I was thinking the base case is $2^1$ vertices, and therefore ...
3
votes
1answer
133 views

When can the coinduction hypothesis be used?

We can use the induction hypothesis when we are proving a property for a structure that is well-ordered. I am aware that there is a proof for this. When it comes to coinduction, I'm confused. One of ...
0
votes
1answer
148 views

Prove that a red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$

I cannot understand the first paragraph of the proof, which comes from the known book Introduction to Algorithms, third-edition, and I consider it has some errors, could anyone help me check about it? ...
-1
votes
2answers
3k views

Proving that $S^* = (S^*)^*$

I am going through some past exam paper questions on regular languages for some revision, and I am having a bit of trouble with converting general ideas into formal mathematical proofs. The question ...
3
votes
0answers
49 views

Induction pitfalls with O notation and recursion

I read the following in CLRS 3rd Ed: I'm not sure I understand exactly how to avoid this pitfall. How would one know that the $\mathcal{O}$ notation in this case grows with $n$ and is thus not ...
4
votes
1answer
74 views

Which inductive schemes can encode the following Agda definition?

Which induction schemes (e.g. induction-recursion by Dybjer and Setzer, "Irish" induction-recursion by McBride or induction-induction by Forsberg and Setzer or perhaps some simpler ones) allow one to ...
4
votes
1answer
623 views

Induction to prove equivalence of a recursive and iterative algorithm for Towers of Hanoi

Using induction how do you prove that two algorithm implementations, one recursive and the other iterative, of the Towers of Hanoi perform identical move operations? The implementations are as follows....
1
vote
2answers
59 views

How do I approach inductive design problems with no information or context given?

As a starting point for our course in Artificial Intelligence, we are being taught induction. We received a number of homework assignments where we have to show our inductive approach for a given ...
2
votes
3answers
220 views

solving a problem with induction

The original question is the following prove that $2·\sum_{i=0}^{n-1} 3^{i} = 3^n-1$ for all n $\geq$ 1 I know that I have to prove by induction and have successfully done the base case, my IH is ...
12
votes
1answer
2k views

What is induction-induction?

What is induction-induction? The resources I found are: the HoTT book, at the end of chapter 5.7. nLab's article a paper called Inductive-inductive definitions this blog post also mentions inductive-...
2
votes
1answer
86 views

Deriving recursive definition from function specification

Given this function specification, where name xs is bound to a list, # denotes its cardinality and ...
1
vote
0answers
35 views

Hanoi towers recursive expression for EVERY algorithm

What the recursive algorithm for moving $n$ disks says, is: If $n > 1$, move $n-1$ discs from A to B. Move the $n$th disk from A to C. If $n > 1$, move $n-1$ discs from B to C. Let $T_n$ be ...
0
votes
0answers
85 views

Prove grade-school multiplication algorithm applied to binary numbers

I want to prove that the basic multiplication algorithm is correct when applied to binary numbers. I try to follow the steps described here and here but didn't succeed. The basic implementation ...
5
votes
0answers
57 views

Rules for consistency with mutual inductive families?

I'm trying to use a proof assistant to define a type and a relation that are mutually dependent on each other: ...
1
vote
0answers
175 views

How to prove a recursive's function Big-Theta without using repeated substitution, master theorem, or having the closed form?

I have a function defined: $V(j, k)$ where $j, k \in \mathbb{N}$ and $t > 0 \in \mathbb{N}$ and $1 \leq q \leq j - 1$. Note $\mathbb{N}$ includes $0$. $V(j, k) = \begin{cases} tj & k \leq 2 \\...
2
votes
1answer
36 views

Proving that a property is k-inductive with an SMT solver (parametric resettable counter)

I'm following the slides at https://homepage.cs.uiowa.edu/~tinelli/talks/FT-11.pdf where Tinelli explains how k-induction works in the context of SMT based model checking. A parametric and resettable ...
1
vote
1answer
200 views

Proving a DFA recognizes a language using induction

The following DFA recognizes the language containing either the substring $101$ or $010$. I need to prove this by using induction. So far, I have managed to split each state up was follows: q0: ...
0
votes
0answers
47 views

Proof that this sorting algorithm sorts the input [duplicate]

I'm given this "sorting" algorithm and now I'm supposed to prove, that if given an array of integers of length $n$, sort(A,0,n-1) will sort it. ...