Prove $8 \mid n^{n+1} + (n+1)^n - 1$

Question

One of my friends is currently taking a first course in pure mathematics + proofs. This is a very self contained course, generally without using techniques taught outside of it. The last question in her first assignment for this course is:

Prove that $8\mid n^{n+1}+(n+1)^n-1$ for all $n \in \mathbb{N}_{>1}$

My first instinct for this question is "use induction!". It turns out they haven't officially learnt induction yet. Then I thought "prove that it's congruent to 0 (mod 8)", but they haven't learned that either. A more elementary approach would be to show that $n^{n+1}+(n+1)^n-1$ is divisible by $2$, then the result of dividing it by $2$ is also divisible by $2$ and so on, three times. There's a nice symmetry with the $a^b+b^a$ but I haven't found any useful properties.

I was originally asked for help but I've been working on it for quite a while and haven't made any progress! Any ideas would be appreciated. (Please don't explicitly write out an answer as this is an assignment question for their class. One of them might be browsing MSE right at this moment!)

Answer 1

Verify the statement holds for $n = 2$.

Next, consider the expression $n^{n+1} + (n+1)^n - 1$ when $n = 2k$ is even.

Then we have: $n^{n+1} + (n+1)^{2k} - 1 = n^{n+1} + \Big(((n+1)^{k} - 1)((n+1)^{k} + 1)\Big)$.

Notice that $(n+1)^k - 1$ and $(n+1)^k + 1$ are consecutive evens, so their product is divisible by $8$.

Moreover, $n$ even means that $n \geq 2$, so $n+1 \geq 3$, and $n^{n+1}$ is divisible by $8$ as well.

In the case where $n = 2k+1$ is odd, we have:

$(n+1)^{2k+1} + (n^{k+1} + 1)(n^{k+1} - 1)$.

Again, the first term is an even raised to at least the third power, hence divisible by $8$.

Finally, $n^{k+1} + 1$ and $n^{k+1} - 1$ are consecutive evens, so also divisible by $8$.

This completes the proof, where the main ideas used were:

• breaking into cases;

• factoring a difference of squares; and

• observing that the product of consecutive evens is divisible by eight.

Answer 2

Nice little problem.

We want to prove $8\mid n^{n+1}+(n+1)^n -1 \,\,\forall \, n \in \mathbb{N}_{>1}$

We partition this into two cases based on parity

CASE 1 Suppose $n=2k$ for some $k \in \mathbb{N}_{\ge 1}$ Then we've

$$n^{n+1}+(n+1)^n -1\\ =(2k)^{2k+1}+(2k+1)^{2k}-1 \\ \,\,=2^{2k+1}(k)^{2k+1} +[(2k+1)^2]^k -1 \equiv 1-1 \equiv \,0(mod\,8)$$

We use $2k+1 \ge 3$ and that $1$ is the only quadratic residue of $8$ in $\mathbb{N}\setminus2\mathbb{N}$

CASE2 Suppose $n=2k+1$ for some $k \in \mathbb{N}_{>1}$ Then we've

$$n^{n+1}+(n+1)^n -1\\ =(2k+1)^{2(k+1)}+ (2(k+1))^{2k+1}-1\\ =[(2k+1)^2]^{(k+1)} +2^{2k+1}(k+1)^{2k+1} -1\equiv 0\,(mod 8)$$

The results mentioned in the previous case are used.

QED