0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ There is no error as the final statement is true, but its very badly worded. For example, you assume $P(n)$ is true for all $n\in N$ during your induction step, but this is all you want to show, right? $\endgroup$ – M. Winter May 3 '17 at 15:57
  • $\begingroup$ Your inductive hypothesis should actually state "Suppose $P(n)$ is true for a particular $n$", since that's what you're assuming in order to prove that $P(n+1)$ holds. $\endgroup$ – florence May 3 '17 at 15:58
  • $\begingroup$ This was asked on an exam question in a previous year and so there has to be a mistake in the proof, although i agree it's badly worded, i think it's written like that on purpose $\endgroup$ – electro7912 May 3 '17 at 15:59
  • $\begingroup$ If the question was "find the mistake in the proof" I think it's a matter critique then of logic (the proof is correct). But "Suppose now that P(n) is true for every n∈N" well, that is very incorrectly stated and not at all what is meant. We can't assume what we want to prove! What is meat was that P(n) is true for some unspecified n (but not every n). "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" This also isn't correct. Suppose something was true for P(1) and P(n=5) and P(n+1=6).... $\endgroup$ – fleablood May 3 '17 at 16:25
  • $\begingroup$ Although I will say, if the exam question was "Find the error in the proof...." that is an unfair question as it implies the logic of the proof is false or invalid and a student would naturally look there at the argument and not the expositions. In fact I doubt many professors would look at the exposition. The question would be better as "critique this proof and find its incorrect statements" $\endgroup$ – fleablood May 3 '17 at 17:04
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Also. Since P(1), P(n), and P(n+1) one are true then it is true for all natural numbers doesn't follow unless it is stated that P(n) being true implies P(n+1) is true. $\endgroup$ – fleablood May 3 '17 at 16:49
0
$\begingroup$

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

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

$\endgroup$
0
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ It's correct. But it has errors. $\endgroup$ – fleablood May 3 '17 at 16:41
  • $\begingroup$ @fleablood thanks, I have made an edit. $\endgroup$ – Nitin Uniyal May 4 '17 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.