# Proof of divisibility by induction [duplicate]

I've recently come across a divisibility problem that I am unable to solve. I know that most of these types of problems have fairly straightforward proof-by-induction solutions -- but for this particular problem, I don't know how to finish the inductive step. Or perhaps there is another, easier path to a proof?

Anyways here it is:

Prove that ((n+1)^n) - 1 is divisible by n^2 for all positive integers n.

Thanks in advance!

• I dont think you need induction, by the binomial theorem, each term except the $1^n$ term has at least two factors of $n$, but the minus $1$ gets rid of that pesky last term. – PhysMath May 17 at 23:13
• I suppose the binomial theorem is proved by induction – J. W. Tanner May 17 at 23:16
• There are ways to prove the binomial theorem without induction, regardless, this proof in and of itself does not require induction. – PhysMath May 17 at 23:19
• Special case $\,x = n\,$ in the linked dupe. – Gone May 17 at 23:29
• ... or $\,x= n+1\,$ in the 2nd link. We have tens if not hundreds of questions on variants of this. – Gone May 17 at 23:43

## 2 Answers

Note \begin{align*} (n+1)^n -1 &= \left(\sum_{k=0}^n \binom{n}{k}n^{n-k}\right) - 1\\ &= (n^n + \binom{n}{1}n^{n-1} + \binom{n}{2}n^{n-2} + \dots + \binom{n}{n-1}n^{n-(n-1)} + 1) - 1\\ &= n^n + \binom{n}{1}n^{n-1} + \binom{n}{2}n^{n-2} + \dots + \binom{n}{n-1}n^{n-(n-1)} \end{align*}

Now just convince yourself that every term here has at least $$2$$ copies of $$n$$. In fact, it should be obvious that all but the last term certainly have a factor of $$n^2$$, so really just check that the last term has a factor of $$n^2$$. This should be clear too.

• Why did this get a downvote? It is a simple and correct solution to the problem. – PhysMath May 18 at 17:13

hint

Using the fact that for $$a\ne 1$$,

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

we have

$$(n+1)^n-1=n\Bigl(1+(n+1)+(n+1)^2+...+(n+1)^{n-1}\Bigr)$$

$$=n\Bigl(n+(n+1-1)+((n+1)^2-1)+...((n+1)^{n-1}-1)\Bigr)$$

$$=n^2\Bigl(2+\frac{(n+1)^2-1}{n}+...+\frac{(n+1)^{n-1}-1}{n}\Bigr)$$

• This seems like a very opaque way of looking at it. Now we have to consider all the expansions of all those intermediate terms as well! – Eulerian May 17 at 23:26
• @Eulerian Said more conceptually: apply the double root test (put $\,x = n+1\,$ in the linked answer). – Gone May 17 at 23:40