Proving the Divisibility Result using Inductive Proof

Proof by induction also very useful for proving divisibility results that hold for all values in a sequence

In previous examples, we've seen how to prove that $3^{2n} - 1$ is divisible by $8$ for all $n \geq 1$ .

Here, we'll work through another example from start to finish.

Recall the two key steps in proof by induction:

Base Case: We first the first value of $n$ for which the divisibility result holds (usually $n=1$ or $n=0$ ). This is like pushing over the first domino.
Inductive Step: We assume the formula is true for some arbitrary term $k$ , and then use this assumption to prove that it must also be true when we add the next term, $k+1$ . This is like showing that if one domino falls, it will knock over the next one.

...