My Favourite Proof

This post is inspired and adapted from Greg Martin's excellent talk on prime numbers (found here).

As a student of mathematics, one of the first things I ever learned was the concept of a proof. In fact, the first proof I ever saw was Euclid's classic proof that there were an infinite number of primes.

If you have never seen Euclid's proof before, it goes something like this:

Suppose there were a finite number of primes. We may label them $p_1, p_2, \ldots, p_n$. Let $$N=p_1 p_2 \ldots p_n + 1.$$ Now for every prime $p_i,\,1\leq i\leq n$ that we just labelled, the remainder of $N$ divided by $p_i$ is 1. However, since $N$ is not prime, $N$ must be able to be factorized into a product of primes. What primes are in that factorization if it doesn't contain any of the primes we just listed out?

Hence, $N$ must have some new prime in its factorization or be a prime itself. This contradicts our assumption that there are a finite number of primes, and therefore an infinite number of primes must exist. $\blacksquare$

Recently, I learned that a variant of Euclid’s proof can be used to prove the infinitude of primes of the form 4k-1 and 6k-1. The proof for 4k-1 is below:

Suppose there are a finite number of primes that is of the form 4k-1 for some $k\in\mathbb{N}$. Again, we may label them $p_1, p_2, \ldots, p_n$. Let    $$N=4 p_1 p_2 \ldots p_n - 1.$$ Again, for every prime $p_i,\,1\leq i\leq n$ that we just labelled, the remainder of $N$ divided by $p_i$ is 1. Note that $N$ is not prime since it is of the form 4k-1 but greater than any of our $p_i$. However, since $N$ is not a prime, $N$ must be able to be factorized into a product of primes. 

Furthermore, the factorization of $N$ must only contain primes of the form 4k+1 since $N$ is odd and all primes of the form 4k-1 are used. This is a contradiction since two numbers which are of the form 4k+1 must have a product of the form 4k+1. Hence, if $N$ was entirely the product of primes of the form 4k+1, $N$ must be a number of the form 4k+1 also. But since $N$ is obviously not expressible as 4k+1, $N$ must itself be a prime that is of the form 4k-1 or have some new prime factor that is of the form 4k-1. Again, by contradiction, there must exist an infinite number of primes of the form 4k-1. The case for 6k-1 is similar. $\blacksquare$

Amazingly, there is a general theorem which states that a Euclid-style proof can only be used to prove the infinitude of primes of the form $p \equiv a\bmod{m}$, where $a^2 \equiv 1 \bmod{m}$ for any two natural numbers $a$ and $m$ (proven here by Murty, 1988). For example, this means that infinitude any primes of the form $p \equiv -1 \bmod 4$ may be proven (as we did above), but any primes of the form $p \equiv 3 \bmod 7$ cannot be proven by Euclid's proof.

I find Euclid’s classic proof of the infinitude of primes beautiful -- not just because it establishes an amazing result in an elegant way, but because of its vast reusability. For these reasons, it is easily my favourite proof.

Bonus: From the theorem above, we may also prove infinitude of primes of the form 4k+1 by a Euclid style proof. Try proving this statement! Be warned though, there is an extra trick to defining $N$ than just multiplying all primes of the form 4k+1 together. The solution can be found in the slides of Greg Martin, as referenced in the first sentence of this post.

First they came...

A very powerful quote that was brought to my attention by a commenter on Hacker News on the proposed Polish Anti-Counterfeiting Trade Agreement. When citizens are inactive on bad government reforms, what seems like one small alteration could build up to monumental changes.

First they came for the communists, and I didn't speak out because I wasn't a communist. 

Then they came for the trade unionists, and I didn't speak out because I wasn't a trade unionist.   

Then they came for the Jews, and I didn't speak out because I wasn't a Jew. 

Then they came for the Catholics, and I didn't speak out because I was Protestant. 

Then they came for me and there was no one left to speak out for me.

Martin Niemöller - First They Came

Prove this identity

A note to future me:

Today you were trying to do probability questions with your pathetically sad probability skills and you found that
$$\sum_{i=0}^{n-1}\frac{m}{t-i}\frac{\binom{t-m}{i}}{\binom{t}{i}}=1-\frac{\binom{t-m}{n}}{\binom{t}{n}}.$$
Dare you to prove it.

From,
Your arrogant younger self.

Here's a hint:
$$\frac{\binom{t-m}{i}}{\binom{t}{i}}=\frac{\binom{t-i}{m}}{\binom{t}{m}}.$$
Why? Can you think of a combinatorial interpretation for this? Proving it through algebra is trivial. Thinking of an interpretation may lead to some actual learning.

Bonus:
From the identity above, you also managed to find that it implies: $$\sum _{i=0}^n \binom{t-i}{m}=\binom{t+1}{m+1}-\binom{t-n}{m+1}.$$  Prove this identity.

A curious identity

I was trying to do a question the other day when I found an interesting identity that is a corollary of the double angle formulae. I've searched online for its name, but it might be so trivial that it doesn't have one. Instead of revealing the identity, I'll let you figure it out for yourself:
$$\frac{1}{2^0}\cos(x_1) = \cos(x_1)$$
$$\frac{1}{2^1}\left(\cos(x_1+x_2)+\cos(x_1-x_2)\right)=\cos(x_1)\cos(x_2)$$
$$\frac{1}{2^{2}}\left(\begin{array}{c} \phantom{+}\cos(x_{1}+x_{2}+x_{3})\\ +\cos(x_{1}+x_{2}-x_{3})\\ +\cos(x_{1}-x_{2}+x_{3})\\ +\cos(x_{1}-x_{2}-x_{3})\end{array}\right)=\cos(x_{1})\cos(x_{2})\cos(x_{3})$$
Do you see the pattern?
Can you prove the pattern (Hint: Try induction)?
Are there other similar identities involving sines and combinations of sines and cosines?

For those who are curious, the question that led me to this identity was:
Determine the value of $$\cos\left(\frac{\pi}{7}\right)\cos\left(\frac{2\pi}{7}\right)\cos\left(\frac{4\pi}{7}\right).$$

There is a simple way to do this question, and a hard way. Sadly the identity I found led to the hard way.