Let $n\in\mathbb{Z}^+$, and let $p$ be a prime number. Prove by induction that $n^p$ can be expressed as the sum of $n$ and some multiple of $p$.

Question

I have a problem with approaching this problem. I am not sure how to handle $2$ variables ($n$ and $p$) during induction in this context. I am aware that normally you have $2$ induction steps for $2$ variable induction. But I am not able to apply it here.

Thanks in advance.

Answer 1

Sketch of Inductive Step:

Observe that (using the binomial theorem)

$$ (n+1)^p=n^p+\binom{p}{1}n^{p-1}+\binom{p}{2}n^{p-2}+\dots+\binom{p}{p-2}n^2+\binom{p}{p-1}n+1. $$

• Use the inductive hypothesis to rewrite $n^p$

• Show that all the binomial coefficients appearing above are divisible by $p$ (hint: $p$ is prime, so it can't be cancelled out).

• Regroup your terms to get the expression in the right form for the result for $n+1$.