For the past two years, I’ve been writing a blog post each month featuring common mistakes that students make, tools to make students’ lives easier, sample problems, and discussions of common course topics. While I’ll be signing off from these monthly blog posts, I’d like to take the time to feature my top picks from the last couple of years: using git, topics in Java programming, and avoiding begging the question in proofs.
Tag: proofs
Practice Problem: Is 3 Irrational?
In a first number theory course, there’s typically a proof that the square root of 2 is irrational. The traditional proof uses the properties of divisibility to arrive at a contradiction. We can even swap a 5 into the proof, in place of the 2, to prove the square root of 5 is irrational. But could we do the same with a 9, and “prove” that the square root of 9 is irrational?
The Cardinality of Natural Numbers and Integers
Both the set of natural numbers and the set of integers are infinite in size. Amazingly, though, they’re exactly the same size. In this blog post, we’ll explore a technique for showing that these two infinite-sized sets have equal cardinality: creating a bijection between them. We’ll use this technique to show that, counter to all intuition, there are exactly as many natural numbers as there are integers.
The Pigeonhole Principle and Hash Tables
This blog post describes what the pigeonhole principle states, demonstrates how to prove its correctness by contrapositive, then applies the pigeonhole principle to the hash table data structure. After reading this post, you should understand how to prove the pigeonhole principle, and recognize situations in computer science where it applies.
Reversing Your Approach to Induction
After reading this post, you should feel comfortable writing proofs by induction in the order of inductive step first, followed by base cases. You should be able to use this method of writing proofs to identify the correct base cases in problems where it is not clear how many or which base cases are necessary.