2022 Developer Survey is open! Take survey.

Questions tagged [induction]

Questions about mathematical induction and inductive proofs.

Filter by
Sorted by
Tagged with
0 votes
1 answer
37 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: ...
user avatar
1 vote
1 answer
51 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 ...
user avatar
0 votes
1 answer
22 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 $...
user avatar
  • 1
2 votes
1 answer
50 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$ ...
user avatar
1 vote
1 answer
34 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 ...
user avatar
  • 1,873
0 votes
1 answer
34 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. ...
user avatar
  • 293
0 votes
0 answers
14 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 ...
user avatar
2 votes
1 answer
66 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 \...
user avatar
1 vote
2 answers
101 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, ...
user avatar
0 votes
1 answer
41 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?
user avatar
0 votes
1 answer
48 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 ...
user avatar
1 vote
1 answer
20 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 ...
user avatar
  • 61
2 votes
1 answer
77 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 $...
user avatar
3 votes
2 answers
217 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)$ ...
user avatar
1 vote
1 answer
38 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\...
user avatar
1 vote
1 answer
92 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 ...
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....
user avatar
  • 115
1 vote
1 answer
425 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
  • 113
1 vote
1 answer
325 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 ...
user avatar
0 votes
3 answers
152 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]...
user avatar
0 votes
1 answer
38 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^...
user avatar
  • 123
0 votes
2 answers
121 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 ...
user avatar
  • 147
1 vote
1 answer
20 views

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

The following algorithm constructs a binary tree. ...
user avatar
  • 73
0 votes
2 answers
84 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 ...
user avatar
  • 123
0 votes
1 answer
158 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$? ...
user avatar
1 vote
1 answer
55 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 ...
user avatar
  • 113
1 vote
1 answer
37 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 \:...
user avatar
  • 13
0 votes
1 answer
65 views

how can i prove the following algorithm?

...
user avatar
1 vote
1 answer
63 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 ...
user avatar
1 vote
1 answer
35 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 ...
user avatar
0 votes
0 answers
31 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 ...
user avatar
  • 101
11 votes
12 answers
9k 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 ...
user avatar
  • 231
0 votes
1 answer
72 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 ...
user avatar
1 vote
1 answer
90 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 ...
user avatar
1 vote
1 answer
61 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)$
user avatar
0 votes
1 answer
208 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 ...
user avatar
0 votes
1 answer
173 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? ...
user avatar
  • 241
3 votes
1 answer
146 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 ...
user avatar
  • 133
3 votes
0 answers
58 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 ...
user avatar
4 votes
1 answer
80 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 ...
user avatar
2 votes
3 answers
223 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 ...
user avatar
  • 33
2 votes
1 answer
89 views

Deriving recursive definition from function specification

Given this function specification, where name xs is bound to a list, # denotes its cardinality and ...
user avatar
  • 125
1 vote
0 answers
42 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 ...
user avatar
  • 133
0 votes
0 answers
87 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 ...
user avatar
  • 101
5 votes
0 answers
60 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: ...
user avatar
  • 29.1k
1 vote
0 answers
188 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 \\...
user avatar
2 votes
1 answer
37 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 ...
user avatar
1 vote
1 answer
250 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: ...
user avatar
  • 33
0 votes
0 answers
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. ...
user avatar
1 vote
1 answer
725 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 ...
user avatar
  • 165