Tag Archives: proof

Ways to prove a bijection

You have a function and want to prove it is a bijection. What can you do? By the book A bijection is defined as a function which is both one-to-one and onto. So prove that is one-to-one, and prove that … Continue reading

Posted in logic, proof | Tagged , , , , , , , , | 6 Comments

A simple proof of the quadratic formula

If you’re reading this blog you have probably memorized (or used to have memorized) the quadratic formula, which can be used to solve quadratic equations of the form But do you know how to derive the formula? Usually the derivation … Continue reading

Posted in algebra, proof | Tagged , , , , | 3 Comments

PIE: proof by counting

Recall the setup: we have a universal set and a collection of subsets , , , and so on, up to . PIE claims that we can compute the number of elements of that are in none of the (that … Continue reading

Posted in combinatorics, pattern, proof | Tagged , , , , | 1 Comment

PIE: proof by algebra

In my previous post I stated a very formal, general form of the Principle of Inclusion-Exclusion, or PIE.1 In this post I am going to outline one proof of PIE. I’m not going to give a completely formal proof, because … Continue reading

Posted in combinatorics, induction, pattern, proof | Tagged , , , , , , | 2 Comments

Computing the Euler totient function, part 3: proving phi is multiplicative

We are trying to show that the Euler totient function , which counts how many numbers from to share no common factors with , is multiplicative, that is, whenever and share no common factors. In my previous post, we looked … Continue reading

Posted in arithmetic, computation, counting | Tagged , , , | 1 Comment

Chinese Remainder Theorem proof

In my previous post I stated the Chinese Remainder Theorem, which says that if and are relatively prime, then the function is a bijection between the set and the set of pairs (remember that the notation means the set ). … Continue reading

Posted in modular arithmetic, number theory | Tagged , , , | 2 Comments

Efficiency of repeated squaring: another proof

In my previous post I proved that the “binary algorithm” (corresponding to the binary expansion of a number ) is the most efficient way to build using only doubling and incrementing steps. Today I want to explain another nice proof, … Continue reading

Posted in computation, proof | Tagged , , , , , , , , | 3 Comments