# Questions tagged [proof-techniques]

Questions about general methods and techniques for proving multiple theorems. When asking about the proof of a single statement, use tags relating to what the proof is about instead.

641 questions
Filter by
Sorted by
Tagged with
49 views

### Why discriminate the base case allows me to complete the induction proof?

I have a successful completed proof which used induction. but I essentially proved the goal on the base case by tactic discriminate. Why is this induction proof ...
34 views

### Converse proof for random coding capacity of AVC

I want to see the converse proof for the random coding (shared randomness) capacity of AVC. All I can find online is Csiszar Narayan's AVC paper which looks at deterministic coding. Further, the proof ...
59 views

76 views

175 views

### Double hashing constraints

For double hashing, we have some constraints on $h'(k)$ (1) It should never evaluate to 0 (2) It should be relatively prime to m How to show that all slots in an open addressing table will be ...
73 views

### Proving van Emde Boas recurrence

I have tried to solve the following question: van Emde Boas Bounds Show that $T(u) = T(\sqrt{u}) + O(1)$ has the solution $T(u) = O(\log\log u)$. Hint: consider the binary representation of $u$. ...
78 views

214 views

### Proof of a greedy algorithm used for a variation of bin-packing problem

We are given an array of weights $W$ (all weights are positive integers), and we need to put the weights inside bins. Each bin can hold a maximum of Max_val, and each weight is at most Max_val. The ...
137 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? ...
34 views

### Accessible CS Math Job [closed]

I am a CS undergrad and a huge enthusiast of pure math. I have been doing competitive programming and proofs for a while. My ambition is to become an academic in theoretical computer science. The ...