Use induction to prove that $3 |(7^n −1)$ for every natural number n.

Question

This is what I have so far and now I'm getting lost.

Proof - We prove by induction. Let $P(n)$ be the statement "$3|(7^n - 1)$". Since $3|6$, we see that $P(1)$ holds. Suppose that is true for $n = k$. We must show the result is true for $n = k + 1$.

Consider,

$$ 7^{(k+1)} - 1 = (7-1)(7^k + 7^{(k-1)} + \cdots + 1) = 6(7^k + 7^{(k-1)} + \cdots + 1)$$

I do not know if I am doing it correctly or if I assumed my goal.

Answer 1

I'm assuming you meant to write in parentheses: $$7^k + 7^{k-1} +\dots+7^0$$ In which case this is fine, although you're not using the induction hypotheses to prove the induction step and therefore there is no reason to prove this by induction. The proof you gave works at once for all k.

Answer 2

Step $\boldsymbol 0$. Clearly $3|0$, hence $ 3|(7^0-1)$.

Inductive step. Now suppose $3|\,(7^{n-1}-1) $ for some $n\ge 1$; then $7^{n-1}=3k+1 $ for some integer $k$. Hence $$ 7^{n}-1=7\cdot (3k+1)-1=21 k+6=3(7k+2), $$ implying $3| \,(7^{n}-1)$.

Answer 3

Assume that $6 \mid (7^k - 1)$ is true so that we can write,

$\tag 1 7^{k} - 1 = 6s $

Using Euclidean division on the dividend $7^{k+1} - 1$ we can write as true

$\tag 2 7^{k+1} - 1 = 6t + r \quad \text{ with } 0 \le r \lt 6$

By $\text{(1)}$, we can write

$\tag 3 7^{k+1} - 7 = (6 \times 7)s$

Subtracting $\text{(3)}$ from $\text{(2)}$ (lhs/rhs),

$\tag 4 6 = 6 (t - 7s) + r$

By applying the theory of Euclidean division to $\text{(4)}$, we conclude that $r= 0$, and the inductive step has been proved.

---

Reviewing the above argument we can now state and easily prove the following,

$\quad \text{If } 7^{k} - 1 = 6s \text{ then } 7^{k+1} - 1 = 6(7s+1)$

Answer 4

Your proof is valid if we assume that we know that $a^{m+1} - b^{m+1}=(a^m + ba^{m-1} + ... + b^{m-1}a + b^m)$.

But if we do know that then your proof is one line: $7^n - 1=(7-1)(7^{m-1}+...+1) = 6*(7^{m-1}+...+1)$ and no need for induction at all.

So I'm assuming you aren't supposed to know that result. But could you prove the result?

To do it without the result we can do

Induction step: Assume $6|7^k-1$

then $7^{k+1}-1 = 7*7^k- 1 = (6+1)7^k - 1=$

$6*7^k + (7^k -1)$ and $6|6*7^k$ and $6|7^k-1$ so $6|6*7^k + (7^k -1)$

....

or you could just prove the result

You can prove it by induction:

$a^1-b^1 = (a-b)$

Induction step:

Assume $a^k - b^k = (a-b)(a^{k-1} + a^{k-2}b + ... +ab^{k-2} + b^{k-1})$

Then $a^{k+1} -b^{k+1} =(a*a^{k} - a*b^k)+(a*b^k- b*b^k)=$

$a(a^k-b^k) +(a-b)b^k =$

$(a-b)a(a^{k-1} + a^{k-2}b + ... + ab^{k-2} + b^{k-1}) + (a-b)b^k=$

$(a-b)[a(a^{k-1} + a^{k-2}b + ... + ab^{k-2} + b^{k-1}) + b^k]=$

$(a-b)[(a^k + a^{k-1}b + .... +a^2b^{k-2} + ab^{k-1}) + b^k]=$

$(a-b)(a^k + a^{k-1}b + .... +a^2b^{k-2} + ab^{k-1} + b^k$

Now the result is proven you can use it.

.....