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.

Life keywords

A few keywords for life that everybody should be doing on a regular basis. 🙂

Life. Family. Love. Health. Work. Improve/Grow. Socialize. (Keep) Try(ing). Patience. Belief. Balance. Food. Rest. Relax. Think.

If you can do most of these, you should be happy and consider yourself lucky.

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.

…and in JavaScript, using Sweet.js

This post is a continuation of my previous post, Capturing abstractions in Lisp.

Today I was playing with Sweet.JS, a JavaScript library that adds the possibility to make macros within the language.

I went through the tutorial and it is pretty straight-forward.

// delay needs to be a macro in order for the code to work correctly.
// Otherwise the invocation of delay will evaluate all its arguments eagerly.
syntax delay = function (ctx) {
    let x = ctx.next().value;
    return #`(function() { return ${x} })`;
}

// similarly for cons-stream
syntax cons_stream = function(ctx) {
    const [...args] = ctx.next().value.inner();

    let param1 = args[0];
    let param2 = args.slice(2);

    return #`([${param1}].concat(delay(${param2})))`;
}

// force just evaluates
function force(x) {
    return x();
}

function next_integer(x) {
    return cons_stream(x, next_integer(x+1));
}

function all_positive_integers() {
    return next_integer(0);
}

function integer_ref(list, j) {
    if (j == 0) {
        return list[0];
    } else {
        return integer_ref(force(list[1]), j - 1);
    }
}

var integers = all_positive_integers();
// display 100th number:
console.log(integer_ref(integers, 100));

With this code snippet, we can see that using this library we get a very powerful Lisp-like syntax 🙂