Square of product of successive naturals

I’ve been working on an interesting task from a regional math contest:

Prove that the product of 8 successive naturals cannot be a natural number to the power of 4.

To prove this, we will first take a look at two other theorems (and prove them), and then use them to prove the original statement.

I. $\sqrt{x}$ irrational $\implies \sqrt{\sqrt{x}}$ irrational

To prove this, it suffices proving the contrapositive:
$\sqrt{\sqrt{x}}$ rational $\implies \sqrt{x}$ rational.

We have that for some a, b, $a/b = \sqrt{\sqrt{x}}$

Square both sides to get $a^2/b^2 = \sqrt{x}$ . Thus, $\sqrt{x}$ is rational.

II. $\sqrt{x(x+1)}$ is irrational

To prove this, note that x and (x+1) need to be squares. Consider for some a, $x = a^2$ . Further, for some b, $x + 1 = b^2$ .

Now, $b^2 - a^2 = (b - a)(b + a) = 1$ . But the only way this is possible if $b - a = 1/(b + a)$ .

Since a and b are positive naturals, we reach a contradiction for the identity above and thus either x or x+1 have no squares. In either case, $\sqrt{x(x+1)}$ is irrational.

III. Prove that there is no y s.t. $y^4 = x(x+1)(x+2)(x+3)(x+4)(x+5)(x+6)(x+7) = *$

We will assume that such y exists and reach a contradiction.

Rewrite as $y = \sqrt{\sqrt{*}}$ and suppose y is rational.

From I we have that it suffices to only prove that $\sqrt{*}$ is rational.

From II we have that either x or (x+1) is irrational. At least one of the 8 elements has no square, and we reach a contradiction. Thus y is irrational.

Consecutive odd primed integers

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.

Proof of the binomial theorem

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]$

Now, by setting $m = j + 1$ we get the induction hypothesis, thus the identity is proven.

Closed-form expression of a recursive function

Let’s suppose, for the funs, that you go to the store and suddenly the manager tells you “For every 2 pieces of milk, you get 1 bonus.”

So you stop and think.
For 2 pieces, you end up having 3.
For 4 pieces, you end up having 2 as a bonus, and another one from that bonus 2 makes 4 + 2 + 1 = 7.
For 8 pieces, you end up having 4 as a bonus, and 2 from the bonus 4 and additional 1 from the bonus 2 makes 8 + 4 + 2 + 1 = 15.
You say, a great deal!

Note here that we don’t discuss the case where you don’t get bonus from the bonuses as that’s not hard to calculate.

Now let’s abstract “For every k pieces, you get 1 bonus” and we can start working our way to a closed-form expression.

This was my first attempt to solve it using recursion:

function calc(n, k) {
    if (n < k) {
        return n;
    }
    return n + calc(n / k, k);
}

Cool, let’s give that a try:

> calc(2, 2)
3
> calc(4, 2)
7
> calc(6, 2)
10.5

Seems to be working as expected.

In understanding what that does, let’s try to expand the first few terms manually.
n + (n/k) + (n/k)/k + ((n/k)/k)/k + … = n + n/k + n/k^2 + n/k^3 + … = s
This will proceed until one of the terms is less than k.
Then I went ahead and created a function that calculates the summation (using n/k as upper bound, which seems to be good enough):

/* This function represents the following summation
n/k
Σ n/k^i
i=0

*/
function calc2(n, k) {
    var sum = 0;
    var i;

    for (i = 0; i < n / k; i++) {
        sum += n / Math.pow(k, i);
    }

    return sum;
}

The next thing I did was run a delta check on various ranges to calculate abs(calc – calc2). It was 0.00015 after a few iterations, so seems good.
Now if we multiply s by (k – 1) we get s(k – 1) = nk – n + n – (n/k) + (n/k) + … which follows that s = nk/(k – 1). Note that I used infinity as the upper bound, as in the long run this wouldn’t matter much. It might be a little off for the first values, but eventually it should converge.

function calc3(n, k) {
    return n * k / (k - 1);
}

One thing to note is that the lesser k, the better. Otherwise, the limit as k -> Infinity is equal to just n.
If we now instantiate k to 2, we get n * 2, which means that you pay the milk at 50% discount (in the long run), which is a really good thing!

Elegance of mathematical definitions

As I was working my way through “How To Prove It” by Daniel Velleman, I came across this definition in section 4.4 Ordering Relations:

Definition 4.4.4. Suppose R is a partial order on a set A, B ⊆ A, and b ∈ B. Then b is called an R-smallest element of B (or just a smallest element if R is clear from the context) if ∀x ∈ B(bRx). It is called an R-minimal element (or just a minimal element) if ¬∃x ∈ B(x Rb ∧ x ̸= b).

The definition for R-smallest element was intuitive to me, all it says is that for all x in B, b <= x, i.e. b is smaller than any element in B given all of them are comparable.

The definition for R-minimal was a little trickier to me. Later in the book it’s shown that it’s equivalent to ∀x ∈ B(x Rb → x = b) which is a bit easier to grasp, but still was not intuitive to me.

So the R-minimal is similar to R-smallest one, with the difference that it only applies to comparable elements, and uses xRb instead of bRx.

Given my programming background, I tried to come up with a more intuitive definition:
…b is called an R-minimal element if:
∀x, y ∈ B:
1. b R x (b <= x)
2. y R x (y <= x)
3. b R y or y R b (b <= y or y <= b, i.e. b and y are comparable)
Imply
b R y (b <= y)
This says that for any elements x and y, b will always be lower than those, given they are comparable.

This definition, although a bit larger than the original (elegant) one, made things clearer for me. But how can I verify if this definition is really equivalent to the original one? I tried to come up with a proof and had amnn from #haskell freenode to verify it for me (thanks!). Here’s the proof:

I. b is R-minimal if ∀x ∈ B: x R b → x = b
II. b is R-minimal if ∀x, y ∈ B: b R x ∧ y R x ∧ (b R y ∨ y R b) → b R y
R partial order: reflexive, antisymmetric, transitive.

Prove (or disprove) that I ↔ II.

(→): Suppose ∀x ∈ B: x R b → x = b.
Further suppose that y, z are arbitrary in B: b R y ∧ z R y ∧ (b R z ∨ z R b).
Prove that b R z.

Proof:
Case b R z: Holds trivially.
Case z R b: z = b → b R z.

(←): Suppose ∀x, y ∈ B: b R x ∧ y R x ∧ (b R y ∨ y R b) -> b R y.
Further suppose z is arbitrary in B: z R b.
Prove that z = b.

Proof:
Using universal instantiation, let x = b, y = z: b R b ∧ (z R b ∨ b R z) → b R z.
So given R is partial order (reflexive) we have b R b and we also have z R b from the givens.
With this, we can conclude b R z.
So since R is a partial order and thus antisymmetric,
from b R z and z R b we can conclude that b = z.

After spending some more time on thinking about the original definition, it is quite simple actually, because all it says that nothing is smaller than b. This definition is elegant in my opinion, because it “says” so much stuff with a few simple symbols. It is what inspired me to write this post.