Chapter 9.5, Problem 49E

Solution

To prove : Using mathematical induction that for any integer $a$ greater than 1, $a-1$ divides $a^n-1$ holds true for all positive integers $n$ .

Given information :

The statement for any integer $a$ greater than 1, $a-1$ divides $a^n-1$ holds true for all positive integers $n$ .

Formula used :

Follow the steps to prove that the statement is true for any positive integer.

Anchor step: Prove that any statement $P_n$ is true for $n=1$ .

Inductive hypothesis: Assume $P_n$ is true for $n=k$ .

Inductive Step: Prove that $P_n$ is true for $n=k+1$ .

Proof :

Conjecture:

Take $P_n$ to be statement $P_n:a^n-1$ is divisible by $a-1$ , $a$ is positive integer.

So,

  $a>1$

Anchor step:

Prove that $P_n$ is true for $n=1$ .

For $n=1$ ,

  $a^1-1=a-1$

  $a-1$ is divisible by $a-1$ .

So, $P_1$ holds true.

Inductive hypothesis:

Assume $P_n$ is true for $n=k$ . Replace $n$ with $k$ in $P_n$ .

  $P_k:a^k-1$ is divisible by $a-1$ , $a$ is positive integer.

Inductive Step:

Prove that $P_n$ is true for $n=k+1$ . This means it is needed to be proved that $P_{k+1}$ must be true.

To prove that $P_{k+1}:a^{k+1}-1$ is divisible by $a-1$ , $a$ is positive integer.

Proceed with the inductive hypothesis.

  $P_k:a^k-1$ is divisible by $a-1$ , $a$ is positive integer.

Start from expression in $P_{k+1}$ .

Now,

  $\begin{array}{c}{a}^{k+1}-1=a\cdot a^k-1\\ =\left(a-1+1\right)a^k-1\\ =\left(a-1\right)\cdot a^k+a^k-1\\ =\left(a-1\right)\cdot a^k+\left(a^k-1\right)\end{array}$

As $a^k-1$ is divisible by $a-1$ , and $\left(a-1\right)\cdot a^k$ is also divisible by $a-1$ ,

Thus, $\left(a-1\right)\cdot a^k+\left(a^k-1\right)$ is also divisible by $a-1$ .

So, $a^{k+1}-1$ is also divisible by $a-1$ .

The statement is same as the statement $P_{k+1}$ , so $P_{k+1}$ is true.

So, if $P_n$ is true for $n=k$ , then it is also true for $n=k+1$ .

Conclusion:

As $P_n$ is true for $n=1$ and $P_k$ further implies $P_{k+1}$ , this means $P_n$ is true for $n=2$ , $n=3$ and so on.

By mathematical induction, $P_n:a_n<2$ is true for all positive integers $n$ .