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

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!)

• What are you expecting in an answer? – mrnovice Mar 19 '17 at 2:02
• Well, it is clearly divisible by two. Consider the cases when $n$ is even and when $n$ is odd. That might be a good first step. – Simply Beautiful Art Mar 19 '17 at 2:06
• Yes, but my objection would be that it is in essence considering the cases modulo $2$ – mrnovice Mar 19 '17 at 2:07
• Basically I wanted some ideas for how to approach it to create a ridiculously elementary proof. Anyway I was able to come up with a very "simple" proof just then, it's super ugly though. First calculate the cases up to n = 8. The remaining n, both even and odd, are trivial with the binomial theorem. – Harambe Mar 19 '17 at 2:12

Verify the statement holds for $n = 0$ and $n=1$ by hand.

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.