Share Your Experience: Take the 2024 Developer Survey

# Tag Info

Accepted

### Why are mathematical proofs so hard?

I feel like i am memorizing the proofs rather than learn how to prove You can't learn "how to prove". "Proving" is not a mechanical process, but rather a creative one where you ...
• 13.3k
Accepted

### What is induction-induction?

Supplemental 2016-10-03: I mixed up induction-induction and induction-recursion (not the first time I did that!). My apologies for the mess. I updated the answer to cover both. I find the ...
• 30.8k
Accepted

### Trying to understand this Quicksort Correctness proof

We are indeed assuming $P(k)$ holds for all $k < n$. This is a generalization of the "From $P(n-1)$, we prove $P(n)$" style of proof you're familiar with. The proof you describe is known as the ...
• 14.8k

### Why are mathematical proofs so hard?

As other authors have mentioned, partly because proofs are inherently hard, but also partly because of the cold fact that proofs are not written for the purpose of teaching, even in most textbooks. ...
• 369

### Why are mathematical proofs so hard?

I can certainly recommend the book of G. Polya's, How to Solve It. It is a standard classic, not to be missed. There is a newer book How to Read and Do Proofs: An Introduction to Mathematical Thought ...
• 211

### Trying to understand this Quicksort Correctness proof

This proof uses the principle of complete induction: Suppose that: Base case: $P(1)$ Step: For every $n > 1$, if $P(1),\ldots,P(n-1)$ hold (induction hypothesis) then $P(n)$ also holds....
• 277k

### How does one know what statements in Coq require Induction?

Coq allows one to prove mathematical theorems in a completely formal way. At first, this copes with our experience of doing maths, which is far more informal. Most of the time, people doing maths are ...
• 14.6k

• 14.6k

### Proving property of a term using Induction

A term is defined recursively. You can do induction on recursive types, using structural induction. For instance, suppose we say that a term is something of the form $c$ (a constant), or $t_1+t_2$, ...
• 161k
Accepted

### How to use structural induction to prove law on lists

You'll want a helper lemma to make this endeavor more digestible. Notations for map and subs: I'm going to condense the ...
• 1,097
Accepted

### Induction rules for reflexive, transitive closure

Here's a fully formal articulation in the language of Agda. First, inductive rules correspond to indexed families. ...
• 12.1k
Accepted

### Prove that the number of full nodes plus one is qual to the number of leaves in a nonempty binary tree

Well, an induction proof consists of a base case and an induction step. For trees that is usually structural induction, based on inductive ways trees are built. The base case considers the smallest ...
• 30.8k

### Why does the denotational semantics for a while loop have a existence quantifier?

The existential quantifier is misplaced. This is due to lack of reasonable notation for what needs to be expressed, namely: "if there is $i$ safisfying condition $C$, then use that $i$", where we make ...
• 30.8k
Accepted

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

Let's start with reformulating the two solutions, following Wikipedia. We use A for the source peg, B for the auxiliary peg, and C for the destination peg. Recursive algorithm If $n > 1$, ...
• 277k
Accepted

### Which inductive schemes can encode the following Agda definition?

No scheme that I know of directly encodes that type. Sometimes it's called a "nested" inductive definition. The complication here is that Maybe and ...

### Why are mathematical proofs so hard?

I like Tom's answer: there's no magic bullet but you just need to continue doing exercises and gradually you will develop a better intuition and know how to attack a problem. As for resources, you ...
• 22.6k

### Why are mathematical proofs so hard?

Why are mathematical proofs so hard?... I have to learn data structures and algorithms, My guess is you'll also want to learn about algorithms' space and time complexity, as quantified in big O ...
• 237
Accepted

### Is this graph Hamiltonian?

The complete digraph of $n$ nodes, $K_n$ has $n(n-1)$ edges. Describe a digraph of $n$ nodes with $n(n-1)-\delta$ edges as a digraph "with $\delta$ edges removed". A proof by induction The ...
• 39k

• 3,192