Thursday, 28 March 2013

Update

On Tuesday, 26 March I mentioned that I was surprised that $\frac {4^n - 1} {3}$ was a natural number or to put it slightly more mathematically that $\forall n \in \mathbb{N}, \frac {4^n - 1} {3} = k$ for some $k \in \mathbb{N}$. It isn't quite as surprising as I first thought.

Assume that $\frac {4^n - 1}{3} = k$ then $4^n - 1 = 3k$
Consider $4^{n + 1} - 1 = m$
then $m - 3k = (4^{n + 1} - 1) - (4^n - 1)$
$m - 3k = 4^{n + 1} - 1 - 4^n + 1$
$m - 3k = 4^{n + 1} - 4^n$
$m - 3k = 4^n(4 - 1)$
$m - 3k = 4^n \times 3$
Therefore, $m - 3k$ is a multiple of $3$ and thus $m$ is a multiple of $3$, which means that $4^{n + 1} - 1$ is a multiple of $3$.
So, we have shown that if $4^n - 1$ is a multiple of three then $4^{n + 1} - 1$ is a multiple of $3$. Since we know that when $n = 1$, $4^n - 1 = 3$ which is a multiple of $3$ then all calculations of the form $4^n - 1$ are a multiple of $3$.
Thus, $\frac {4^n - 1}{3} \in \mathbb{N} \forall n \in \mathbb{N}$

There is, of course, nothing remarkable about the choice of $4$ and $3$ in the above proof. It could equally well have been $p \in \mathbb{N}$ giving the following theorem
$\frac {p^n - 1}{p - 1} \in \mathbb{N} \forall n, p \in \mathbb{N}$