Questions tagged [induction]

Questions about mathematical induction and inductive proofs.

Filter by
Sorted by
Tagged with
0
votes
2answers
40 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
1answer
38 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
36 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
16 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
1answer
60 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
2answers
202 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
1answer
17 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
1answer
42 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
0answers
38 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
1answer
175 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
1answer
195 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
1answer
61 views

What Makes an Algorthim Greedy [Graph Coloring Algorithm]

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] rV2 = [1,...
0
votes
1answer
36 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
2answers
74 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
1answer
19 views

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

The following algorithm constructs a binary tree. ...
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 ...
0
votes
1answer
101 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
0answers
21 views

Is Inductive Logic Programming approach applicable to general theories (not just sets of Horn clauses)?

Inductive Logic Programming (https://en.wikipedia.org/wiki/Inductive_logic_programming) find hypothesis theory H for background theory B and set of examples E. ILP algorithms and implementations ...
1
vote
1answer
34 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
35 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 \:...
0
votes
1answer
58 views
1
vote
1answer
43 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
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
28 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 ...
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 ...
0
votes
1answer
62 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
79 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 ...
1
vote
1answer
39 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
193 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 ...
0
votes
1answer
99 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? ...
3
votes
1answer
117 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 ...
3
votes
0answers
47 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
67 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 ...
2
votes
3answers
215 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 ...
2
votes
1answer
84 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
34 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
57 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
50 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
145 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
171 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
44 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. ...
0
votes
1answer
430 views

Recursive definition for the length of a string?

I found a couple of answers online but I don't quite understand why the answer is right: The length of a string is: If a string has no characters, then its length is 0. Otherwise, the length of the ...
0
votes
0answers
113 views

proving DFA stuck

This DFA fulfills: Define a function $diff: \{0,1\}^*\to\Bbb Z$, for $w \in\{0,1\}^*$, $diff(w)=($# of 1's in $w)- ($# of 0's in $w$). Thus, $diff(\epsilon)=0$; $diff(0)=−1$; $diff(1)=1$. Let $L = ...
0
votes
0answers
35 views

dfa subtract multiple of 3 [duplicate]

Define a function 𝑑𝑖𝑓𝑓 ∈{0,1}→ℤ so: for everything w ∈{0,1}, diff w = # of 1's in w- # of 0's in w. Thus: 𝑑𝑖𝑓𝑓 𝜀=0; 𝑑𝑖𝑓𝑓 0=−1; 𝑑𝑖𝑓𝑓 0=−1; Let 𝐿 = {𝑤∈ {0,1} * | 𝑑𝑖𝑓𝑓 𝑤 = 3𝑚 ...
0
votes
2answers
705 views

prove by induction that the complete recursion tree for computing the nth Fibonacci number has n leaves

I have referenced this similar question: Prove correctness of recursive Fibonacci algorithm, using proof by induction *Edit: my professor had a significant typo in this assignment, I have attempted ...
1
vote
0answers
87 views

Inductive proof on Quicksort with Explicit Stacking

Prove by induction that if Quicksort with Explicit Stacking is modified so that the end-points of the larger sublist are stacked, and the other sublist is sorted first, then the maximum stack size is $...
0
votes
1answer
2k views

Is my proof of my greedy algorithm to find subsequence correct?

Credit to KleinBerg and Taros Book Some of your friends have gotten into the burgeoning field of time-series data mining, in which one looks for patterns in sequences of events that occur over time. ...
1
vote
2answers
849 views

Iterative Fibonacci algorithm correctness proof, finding loop invariants

The algorithm take in an integer $n$ and outputs the $n$th number in the Fibonacci sequence ($F_n$). The sequence starts with $F_0$. I am trying to prove the correctness assuming valid input: ...