Questions tagged [induction]
Questions about mathematical induction and inductive proofs.
186 questions
1
vote
1
answer
173
views
First n Super Ugly Numbers Algorithm and Proof
In the first n super ugly numbers problem we are given a list $P$ of primes. A super ugly number is either composite, i.e. the product of two or more primes, or is prime or equal to $1$. We are asked ...
- 71
0
votes
0
answers
35
views
feedback on proving uniqueness of type lemma for λ-terms by structural induction
I'm a beginner and self teaching from this textbook (link).
I'd welcome feedback and guidance on my attempt to prove the Uniqueness of Types Lemma (ex 2.17).
Exercise 2.17
Prove Lemma 2.10.9 (the ‘...
- 395
0
votes
1
answer
89
views
feedback on exercise solution on structural induction for λ-terms
I'd like feedback on my solution to Exercise 2.16 from this textbook (link).
I am a self-teaching beginner, so would welcome guidance that doesn't assume I have a degree in computer science.
Note - I ...
- 395
2
votes
1
answer
197
views
feedback on exercise solution (structural induction on λ-terms)
I'd like feedback on my solution to Exercise 2.16 from this textbook (link).
I am a self-teaching beginner, so would welcome guidance that doesn't assume I have a degree in computer science.
Exercise ...
- 395
2
votes
1
answer
83
views
structural induction textbook explanation does not mention base cases
The textbook on type theory I'm working through briefly introduces the idea of structural induction.
I've attached an image of the given explanation below.
I am moderately familiar with simple ...
- 395
1
vote
2
answers
154
views
How to prove $T(n) = 2T(\lfloor\frac{n}{2}\rfloor) + n$ is $\Omega(n\log n)$?
I know how to prove for $O(n\log n)$, but I'm hitting a roadblock with this one. Here's what I've tried:
The hypothesis is that there exists some $c > 0$ so that $T(n) \geq cn \log n $, by assuming ...
- 11
1
vote
0
answers
41
views
Show that the top trading cycle algorithm is DSIC
Suppose $n$ items are to be allocated to $n$ people using Gale's Top Trading Cycle algorithm. Assume that everyone ranks every house and the orderings are strict, complete and transitive.
How do I ...
- 11
-1
votes
1
answer
79
views
Loop invariant proof, nth fibonacci number
The code below calculates the nth Fibonacci number. Do you know the mathematical formula used in this algorithm? I couldn't prove the loop invariant here.
...
- 11
4
votes
1
answer
454
views
Is there a fully combinatorial version of MLTT without lambda abstraction?
I have been learning MLTT and working on implementing its type checker referencing Coq's core language specification. Currently, I am at the stage of implementing its termination checker. I find it ...
- 173
4
votes
1
answer
117
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 $\{...
- 438
1
vote
1
answer
228
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
143
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 ...
- 187
1
vote
2
answers
258
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 ...
- 187
0
votes
0
answers
736
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
325
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 ...
- 173