I'm trying to prove the following, but can't seem to understand it. Can somebody help?
Prove $6^n - 1$ is always divisible by $5$ for $n \geq 1$.
What I've done:
Base Case:
$n = 1$: $6^1 - 1 = 5$, which is divisible by $5$ so TRUE.
Assume true for $n = k$, where $k \geq 1$:
$6^k - 1 = 5P$.
Should be true for $n = k + 1$
$6^{k + 1} - 1 = 5Q$
$= 6 \cdot 6^k - 1$
However, I am unsure on where to go from here.
Answer
For $n\geq 1$, let $S(n)$ denote the statement
$$
S(n) : 5\mid(6^n-1)\Longleftrightarrow 6^n-1=5m, m\in\mathbb{Z}.
$$
Base case ($n=1$): $S(1)$ says that $5\mid(6^1-1)$, and this is true.
Inductive step: Fix some $k\geq 1$ and assume that $S(k)$ is true where
$$
S(k) : 5\mid(6^k-1)\Longleftrightarrow 6^k-1=5\ell, \ell\in\mathbb{Z}.
$$
To be proved is that $S(k+1)$ follows where
$$
S(k+1) : 5\mid(6^{k+1}-1)\Longleftrightarrow 6^{k+1}-1=5\eta, \eta\in\mathbb{Z}.
$$
Beginning with the left-hand side of $S(k+1)$,
\begin{align}
6^{k+1} - 1 &= 6^k\cdot 6-1\tag{by definition}\\[0.5em]
&= (5\ell+1)\cdot 6-1\tag{by $S(k)$, the ind. hyp.}\\[0.5em]
&= 6\cdot 5\ell+5\tag{expand}\\[0.5em]
&= 5(6\ell+1)\tag{factor out $5$}\\[0.5em]
&= 5\eta.\tag{$\eta=6\ell+1; \eta\in\mathbb{Z}$}
\end{align}
we end up at the right-hand side of $S(k+1)$, completing the inductive step.
Thus, by mathematical induction, the statement $S(n)$ is true for all $n\geq 1$. $\blacksquare$
No comments:
Post a Comment