Skip to main content

# Questions tagged [induction]

Questions about mathematical induction and inductive proofs.

177 questions
Filter by
Sorted by
Tagged with
0 votes
1 answer
2k views

### Complexity calculation using a recurrence relation [duplicate]

I just can't solve this problem, I'm new to reccurences. I have this recurrence $T(n)=n*T(n-1)$ $T(1)=1$ The second term will be: $T(n-1)=(n-1)*T(n-2)$ And so on. It's complexity is O(n!) but i ...
0 votes
1 answer
72 views

### How to read this inductive language definition?

A language $L$ is defined recursively according to the following rules: $λ ∈ L$ If $w ∈ L$, then $bw ∈ L$ and $waa ∈ L$ I am not sure if strings from this language should mix from this definition. ...
4 votes
1 answer
333 views

### Proof on tree size using Isabelle

I'm trying to learn a little bit about Isabelle and proofs in general, and it's uses in Programming Language Theory. I'm following a book, "Concrete Semantics with Isabelle/HOL". I'm still in the ...
1 vote
2 answers
6k views

### Prove correctness of DFA ending with ab

I have the following deterministic finite automaton and I am need to prove correctness of the claim that this automata accepts $\{wab \mid w\in \{a,b\}^*\}$ I know that I need to prove by induction ...
0 votes
1 answer
964 views

### How do you prove two languages are equivalent using the definition of acceptance?

I need to prove that $L(f(M)) = L(M)\cup \{\varepsilon\}$ where $M$ is a DFA and $f$ is the function $f(M) := (Q\cup \{q_f\}, \Sigma, \delta', q_f, F\cup\{q_f\})$ and $q_f$ is a new state not in $Q$ ...
4 votes
2 answers
536 views

0 votes
0 answers
36 views

2 votes
2 answers
442 views

### Rule induction principles in Harper's PFPL

I have a few small questions about section 2.4 ("Rule induction") in Practical Foundations for Programming Languages (p. 19). (1) In the rule induction principles for ...
0 votes
1 answer
158 views

### Mathematical Induction Problem from Concrete Abstractions

This is a problem from 'Concrete Abstractions' which is available free on the web[1]. It's a book similar to SICP. The problem: Exercise 2.16 Consider the following procedure foo: ...
-1 votes
2 answers
3k views

### Induction proof, base case not working but induction step works? [closed]

$1+3+5+...+(2n+3)=n^2+4n$ For this series using induction proof. Base case 1,2,3,.. not working. But induction step works well. Base case is not given in question.
2 votes
2 answers
862 views

### How to apply the substitution method to n/2?

I recently was introduced to solving recurrence bounds by substitution but there's something i don't understand about it. In standard induction proofs you prove a base case, assume it holds for n ...
4 votes
2 answers
17k views

### Prove correctness of recursive Fibonacci algorithm, using proof by induction

I'm studying for the computer science GRE, and as an exercise I need to provide a recursive algorithm to compute Fibonacci numbers and show its correctness by mathematical induction. Here is my ...
7 votes
1 answer
5k views

### Prove correctness of recursive multiplication algorithm

I'm in a first year discrete math course and we started algorithms. I created a recursive algorithm to multiply two numbers together: ...
1 vote
0 answers
140 views

### How to prove the asymptotic upper bound for $T(n) = 2T(\lfloor n/2\rfloor + 17) + n$ is $O(n \log n)$? [duplicate]

I met the problem Show that the solution to $T(n) = 2T(\lfloor n/2\rfloor + 17) + n$ is $O(n \log n)$ while reading Introduction to Algorithm. It's a question about the substitution method for ...
1 vote
0 answers
95 views

### Proving that a BST with N>=1 nodes will have log(N+1) levels

I am trying to prove by induction the following theorem: Use Induction to prove the following fact: for every integer, $N\ge 1$ , a BST with $N$ nodes must have at least $\log( N + 1)$ levels. I've ...
2 votes
0 answers
4k views

### Insertion sort Proof by Induction

I am reading Algorithm design manual by Skiena. It gives proof of Insertion sort by Induction. I am giving the proof described in the below. Consider the correctness of insertion sort, which we ...
0 votes
0 answers
67 views

### How i can use Mathematical induction to prove CFG production? [duplicate]

If I have production $G_n$ $S \rightarrow A_i b_i \quad$ for $1 \le i \le n$ $A_i \rightarrow a_j A_i \mid a_j\quad$ for $1 \le i$ and $i \ne j$ Prove $G_n$ is sub-productions from $2n^2 - n$ ...
5 votes
2 answers
2k views

### Finding nested intervals efficiently

The intervals are represented as two numbers, e.g. $(4.3, 5.6)$. The intervals are unique. If for $(x,y)$ and $(u,v)$, $x≤u$ and $v≤y$, $(u,v)$ is nested in $(x,y)$ How do I find out which ...
11 votes
3 answers
892 views

### Do "inductively" and "recursively" have very similar meanings?

Do "inductively" and "recursively" mean very similar? For example, if there is an algorithm that determines a n-dim vector by determine its first k+1 components based on its first k components having ...
5 votes
1 answer
1k views

### How to prove that the pre-order tree traversal algorithm terminates?

I see structural induction the usual way for proving an algorithm's termination property, but it's not that easy to prove by means of induction on a tree algorithm. Now I am struggling on proving that ...
9 votes
1 answer
1k views

### Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$

Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$. The book from which this example is, falsely claims that $T(n) = O(n)$ by guessing $T(n) \leq cn$ and then arguing \$\qquad \...