Find the mistake in the following proof

Question

the question is the same as the title. I'm trying to find the mistake in the following statement:

$Theorem$ For every natural number n, the number $4^n-1$ is divisible by 3.

Proof For a natural number n, let P(n) be the statement that 3 divides $4^n-1$. We start by observing that P(1) is true, since $4^1-1=3$ which is divisible by 3. Suppose now that P(n) is true for every $n ∈ N$. Thus $4^n-1=3k$ for some natural number k. Then

$4^{n+1}-1= 4^n*4-1 = 4(3k+1) -1= 12k + 3 = 3 (4k+1)$

which is divisible by 3. Thus P(n+1) holds. Thus, since P(1) is true, and P(n) and P(n+1) are true, the statement P(n) is true for all natural numbers n, by the principle of induction.

Have no idea where to start. Been trying for a while

Answer 1

The proof would be correct but for sloppy statements which are correct in a "You know what I mean way" but as stated are totally false. And it is important that we see them so we don't fall for them and make invalid proofs. (Although this particular proof is valid.)

1) "Suppose now that P(n) is true for every n∈N."

That is assuming what we want to prove. We can't do that. And if we did assume such a thing we couldn't accept any results from it.

What should be sai is "Suppose that P(n) is true for some non-specified n". At this point it could be true for $n = 32$ but not $n=17$. It is true for $n=1$ so we do know it is true for at least one so we can state that. But we don't want to assume $n$ is $1$. Just that $n$ is some unspecified value so that $P(n)$ is true.

2)"Thus, since P(1) is true, and P(n) and P(n+1) are true, the statement P(n) is true for all natural numbers n, by the principle of induction."

Well, not not quite. Suppose may statement was. "P(n) = N is not a square of a prime" and I note P(1) is true (1 is not prime). And P(n=6) is true and P(n+1 = 7) is true and conclude therefore that this is true for all natural numbers by induction.

What should have been stated was "Since P(1) is true, and P(n) being true will imply P(n+1) is true, then P(n) is true for all $n$ by induction."

It is essential that P(n+1) being true is true via a direct inference for a non-specific $n$ where $P(n)$ is true. If $P(n+1)$ is true via a pure coincidence or from the specifics of $n$, we can't make any general conclusions.

(Also, nitpicky, the statement "P(1), P(n) and P(n+1) are true" is a bit meaningless. P(n) is true? For what $n$, when did we ever show that? At one point we assumed it but we never showed it. And how can we say $P(n)$ is true if we never stated what $n$ is? What is meant is $P(n)$ is true for some $n$. But then $P(n+1)$ is true for some $n+1$ and those two statements mean nothing unless there is some implication that for any true P(n) then P(n+1) is true.)

With those corrections the proof is completely valid.

Answer 2

Written clearly, this should look somehow like this.

Let $P(n)\equiv 4^n-1$ is a multiple of $3$. We want to show $P(n)$ for all $n\in \Bbb N$ by induction in $n$.

Induction base: $4^1-1=3$, hence $P(1)$ is satified.

Induction step: Assume $P(n)$ holds. This means there is a $k$, so that $4^n-1=3k$. We can conclude now

$$4^{n+1}-1=4^n\cdot 4-1=(3k+1)\cdot 4-1=12k+3=3(4k+1),$$

hence $P(n+1)$. This proves the statement $P(n)$ for all $n\in \Bbb N$ by induction. $\square$

If there is really a mistake hidden in there, then it is probably the wording of the induction assumption. You wrote "assume $P(n)$ for all $n\in\Bbb N$" but you should only assume it for $n-1$ or all $n'$ smaller than your next step.

Answer 3

Statement should be let $P(k)$ be true for $n = k$.

Then you have to continue for $n = k + 1$.

Answer 4

As per the text you have written,your proof is correct.

Edit: You should start the proof with the step called Basis of induction i.e. $P(1)$ is true as $4^1-1$ is divisible by $3$. Then assume that $P(k)$ is true and using this assumption (this step is Induction hypothesis), try proving that $P(k+1)$ is true (called Induction step which you have done already without any flaws).