# Tag Archives: proof

## The Natural Number Game

Hello everyone! It has been quite a while since I have written anything here—my last post was in March 2020, and since then I have been overwhelmed dealing with online and hybrid teaching, plus a newborn (who is now almost … Continue reading

Posted in challenges, computation, proof | Tagged , , , , , | 6 Comments

## 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 | | 7 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 | | 3 Comments

## Efficiency of repeated squaring: proof

My last post proposed a claim: The binary algorithm is the most efficient way to build using only doubling and incrementing steps. That is, any other way to build by doubling and incrementing uses an equal or greater number of … Continue reading

Posted in computation, proof | | 2 Comments

## The chromatic number of the plane, part 4: an upper bound

In my previous posts I explained lower bounds for the Hadwiger-Nelson problem: we know that the chromatic number of the plane is at least 5 because there exist unit distance graphs which we know need at least 5 colors. Someday, … Continue reading

Posted in geometry, proof | Tagged , , , , , , | Comments Off on The chromatic number of the plane, part 4: an upper bound