0
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – PhysMath May 17 at 23:13
  • $\begingroup$ I suppose the binomial theorem is proved by induction $\endgroup$ – J. W. Tanner May 17 at 23:16
  • $\begingroup$ There are ways to prove the binomial theorem without induction, regardless, this proof in and of itself does not require induction. $\endgroup$ – PhysMath May 17 at 23:19
  • $\begingroup$ Special case $\,x = n\,$ in the linked dupe. $\endgroup$ – Gone May 17 at 23:29
  • $\begingroup$ ... or $\,x= n+1\,$ in the 2nd link. We have tens if not hundreds of questions on variants of this. $\endgroup$ – Gone May 17 at 23:43
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why did this get a downvote? It is a simple and correct solution to the problem. $\endgroup$ – PhysMath May 18 at 17:13
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – Eulerian May 17 at 23:26
  • $\begingroup$ @Eulerian Said more conceptually: apply the double root test (put $\,x = n+1\,$ in the linked answer). $\endgroup$ – Gone May 17 at 23:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.