December 2016 – bor0's reflective blog

A few years ago, for some reason (I don’t remember exactly what it was) I thought of the following problem and tackled around a solution for it:

Prove that the triplet $(3, 5, 7)$ is the only triplet of consecutive odd integers such that all integers in it are primes.

In other words, prove that $\exists! n \in N (2n + 1, 2n + 3, 2n + 5)$ are primes.

We already know if we set $n = 1$ that we get the triplet $(3, 5, 7)$ , but as for the part of proving that this is unique, we need to show that at least one member of the triplet is divisible by 3. So, for example, for $n = 3$ we have $(7, 9, 11)$ , and 9 is not a prime because it’s divisible by 3.

We can use induction on n. The base case is already there for $n = 1$ , so for the inductive step we can assume that either of the members is divisible by 3 (but not the remaining). Now assuming one of the members in $(2n + 1, 2n + 3, 2n + 5)$ is divisible by 3, we need to show that one of the members in $(2n + 3, 2n + 5, 2n + 7)$ is divisible by 3.

From here, we have 3 cases:

$2n + 1$ is divisible by 3. Then, so is $2n + 4$ , and $2n + 7$ , thus one of $(2n + 3, 2n + 5, 2n + 7)$ is divisible by 3.
$2n + 3$ is divisible by 3. Thus one of $(2n + 3, 2n + 5, 2n + 7)$ is divisible by 3.
$2n + 5$ is divisible by 3. Thus one of $(2n + 3, 2n + 5, 2n + 7)$ is divisible by 3.

So, since at least one member of $(2n + 1, 2n + 3, 2n + 5)$ is divisible by 3, but only 3 is a prime (and not multiples of 3 of course), we get that $(3, 5, 7)$ is the only triplet of consecutive odd integers such that all members are prime.

While working on How To Prove It, I found this in the exercises.
To me, the binomial formula is really trivial, but it’s an interesting thing to prove because it requires manipulating summations and some algebra tricks. So let’s get started.

Prove that for all real number x and y, and every natural n:
$(x+y)^n = \sum_{k=0}^{n} {n \choose k} x^{n-k} y^k$
We will use mathematical induction on n.

Base case:
$n = 0: (x+y)^0 = 1 = {0 \choose 0} x^0 y^0$

Inductive hypothesis:
Assume that the formula holds for $n = j$ :
$(x+y)^j = \sum_{k=0}^{j} {j \choose k} x^{j-k} y^k$

Using this identity we need to show that it also holds for $n = j + 1$ .

Multiply both sides of the inductive hypothesis by $x + y$ :
$(x+y)^{j+1} = (x+y)\sum_{k=0}^{j} {j \choose k} x^{j-k} y^k$

Now we can split the summation like so:
$(x+y)^{j+1} = \sum_{k=0}^{j} {j \choose k} x^{j-k+1} y^k + \sum_{k=0}^{j} {j \choose k} x^{j-k+1} y^{k+1}$

Consume the first element of the first summation:
$(x+y)^{j+1} = x^{j+1} + \sum_{k=1}^{j} {j \choose k} x^{j-k+1} y^k + \sum_{k=0}^{j} {j \choose k} x^{j-k} y^{k+1}$

Consume the last element of second summation:
$(x+y)^{j+1} = x^{j+1} + y^{j+1} + \sum_{k=1}^{j} {j \choose k} x^{j-k+1} y^k + \sum_{k=0}^{j-1} {j \choose k} x^{j-k} y^{k+1}$

Shift the bounds of the second summation to match the first:
$(x+y)^{j+1} = x^{j+1} + y^{j+1} + \sum_{k=1}^{j} {j \choose k} x^{j-k+1} y^k + \sum_{k=1}^{j} {j \choose {k-1}} x^{j-k+1} y^k$

From here, we can factor the same elements:
$(x+y)^{j+1} = x^{j+1} + y^{j+1} + \sum_{k=1}^{j} [x^{j-k+1} y^k] ({j \choose k} + {j \choose k-1})$

We will use the identity ${j \choose k} + {j \choose {k - 1}} = {{j + 1} \choose k}$ to simplify:
$(x+y)^{j+1} = x^{j+1} + y^{j+1} + \sum_{k=1}^{j} {{j + 1} \choose k} [x^{j-k+1} y^k]$

Note that ${{j + 1} \choose 0} x^{j + 1} y^0 = x^{j+1}$ , so we can insert first element of first summation back into the summation by setting lower bound to 0:
$(x+y)^{j+1} = y^{j+1} + \sum_{k=0}^{j} {{j + 1} \choose k} [x^{j-k+1} y^k]$

Apply similar reasoning for the upper bound to move $y^{j+1}$ inside the summation:
$(x+y)^{j+1} = \sum_{k=0}^{j + 1} {{j + 1} \choose k} [x^{j-k+1} y^k]$