Proof of divisibility by induction

Question

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!

Answer 1

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.

Answer 2

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