mathematical induction for divisibility: Is this one a valid proof? If so why?

Question

I must prove that $7^n-1$ $(n \in \mathbb{N})$ is divisible by $6$.

My "inductive step" is as follows:

$7^{n+1}-1 = 7\times 7^n-1 = (6+1)\times 7^n-1 = 6\times 7^n+7^n-1$

So now, $6\times7^n$ is divisible by 6, that's obvious. But what about the other part, the $7^n-1$ ? How do we know that it's also divisible by 6? For that's the one I was supposed to prove isn't it? Or have I just done it? How's that? I'm confused..

According to some resources it is a complete proof, however, it's not clear for me why. Could someone please explain?

---

Ahmed Hussein: $7^n-1$ is divisible by $6$ according to the induction hypothesis.

But as its name indicates, it's only a hypothesis and not a known fact, that's what's bugging me.

Elliot G: Since $6|7^k−1$ ...

How do we know?

Sir Jective: Then we can assume that ...

We're just assuming...

I think now you get what I don't understand. I seem to be missing the point of induction, what I don't understand is: Where do we prove during the process that $6|7^n−1$ so that at the last step we can regard it as a known, proven fact?

Answer 1

The first step of induction is a base case. This is what allows us to make further assumptions. Before we can even begin to use induction, we first have to show the statement for a specific value. In this case since we are trying to show a statement for all $n\in\mathbb{N}$, let's start with $1$. It is clear that $7^1-1=6$ so $$6|7^1-1.$$ Since we now have that fact in hand, we know the property holds for $n=1$. If we can show that $$6|7^1-1\implies 6|7^2-1$$ then we will know that the property holds for $n=2$ since we have proven through other means that it is true for $n=1$. Furthermore, if in addition to proving the above we prove that $$6|7^2-1\implies 6|7^3-1$$ we will know that the property holds for $n=3$ and we could continue in this fashion for however long we wanted. The nice thing about induction is that we can do the cases of $n=2$, $n=3$ and even all $n\geq 4$ at once by proving the statement $$6|7^k-1\implies 6|7^{k+1}-1$$ for all $k\geq 1$ since this statement IN ADDITION to our base case $n=1$ gives us that the statement is true for $n=2$ by using our base case and the statement when $k=1$, for $n=3$ by using the fact that it is true for $n=2$ and our statement when $k=2$, and similarly for any $n\in\mathbb{N}$.

One thing to keep in mind is that an induction must always have BOTH a base case and an inductive step, but many times if the base case is obvious(as is the case here) it may be left out of writing for the sake of brevity. Hopefully this helps.

Answer 2

Perhaps a cleaner way to write it:

Step 1: we see that $6|7-1$

Step 2: assume that $6|7^k-1$ where $k\in\Bbb{N}$

Step 3: then $7^{k+1}-1=7\cdot 7^k-1=6\cdot 7^k+7^k-1$. Since $6|7^k-1$ and $6|6\cdot 7^k$, we have $6|7^{k+1}-1$.

Thus $6|7^n-1$ for all $n\in\Bbb{N}$.

Answer 3

As noted in the comments, you are assuming, as your inductive hypothesis, that $6|7^n-1$. An alternative proof is to factor the expression as $$7^n-1=(7-1)(1+7^2+\cdots+7^{n-1})$$

The edits indicate a confusion about what induction is and how it works. There is a good explanation here: Dominoes and induction, or how does induction work?

Answer 4

To assume your induction hypothesis you should use the base case that $7^0-1=0$ is divisible by $6$. Then we can assume that $7^n-1$ is divisible by $6$.

Answer 5

According to some resources it is a complete proof, however, it's not clear for me why. Could someone please explain?

It is not a complete proof, because in your writeup (as the question currently appears) you didn't include the "base case". What your "inductive step" really proves is this statement:

If $7^n - 1$ is divisible by 6, then $7^{n+1} - 1$ is also divisible by 6.

Note that "assumes", "hypotheses", etc. are different ways of referring to the antecedent (the first clause; the "if" part) in this material conditional statement.

What remains is the base case: For $n = 0$, $7^n - 1 = 7^0 - 1 = 1 - 1 = 0$, which is certainly divisible by zero (because $6 \times 0 = 0$). Having established this base case, it "triggers" the conditional statement (i.e., satisfying the "if" clause) for $n = 1$, and then that triggers it for $n = 2$, and so forth, down the line for all natural numbers $n$ (much like a line of dominoes, as described in some of the other answers).