1

Suppose we have a subset of the set of natural numbers. This set includes 100 numbers that is the first 99 numbers is even and the last number is odd. now, induction can be said that the first number is even(first number mod 2 = 0) and number n + 1 is even, and so on. consequently all numbers are even.this is wrong because last number is odd.why is the wrong answer?

user106557
  • 133
  • How can you do the general step?, this is, how can you show that if $n$ is even then $n+1$ is even?. – Cure Nov 29 '13 at 08:03
  • Whether induction is overall conclusion from minor conclusion ? So if, for example, 50 first numbers are even. induction can be concluded that all even.I knew from induction. Is it wrong? – user106557 Nov 29 '13 at 08:09
  • Yes. If i saw a a black bird a week ago and each day from then a black bird flies over my house I may conclude by induction the fact that tomorrow a black bird will fly over my house; that's how induction in a general sense works, but mathematical induction does not work that way. It requires to proof that if is true for $n$ also is true for $n+1$, then if $n$ is even and you proved that $n+1$ is even, putting $n=99$ tells you that the next number is necessarily even. If there's an exception, you could not have proved that $n$ even implies $n+1$ even. – Cure Nov 29 '13 at 08:14

3 Answers3

1

It doesn't work since you don't have the following for any number $n$ of your subset of $\mathbb{N}$:

\begin{equation} n \text{ is even} \Rightarrow n+1 \text{ is even}. \end{equation}

You clarify this by taking the 99th number of your subset to see that the statement is false.

rokeby
  • 88
  • 7
0

The "inductive" step is to say that if something is true for $n$ then it is true for $n+1$. It's implicit here that this inductive step can performed for ALL $n$. In your example, the inductive step is that if the $n$'th number is even, then so is the $n+1$'th number. The proof of this fact for your example comes from the fact that if $n<99$ then $n+1\leq 99$ which means that the $n+1$'th number must be even by the assumptions of the problem. This does not hold for $n=99$ so the inductive step fails there.

Alex R.
  • 32,771
0

Induction proofs consist in having a case that is true (as you did), then proof through sound facts that if one generic case is true then the next case is true as well (here is where your example fails).

Let's use the following example: every natural number (counting number) is less than 100.

We start with 0. Run the test: $0<100?$ yes! OK we now know that there's at least one case for which this is true. Let's assume that it is true for $n$. Is this true for $n+1$?

Your argument was that I look at $1,2,3,\dots$ and they so seem to satisfy the test. But this is not a sound proof. What do we know about sums an inequalities? There isn't any rule that states $$a<b \Rightarrow a+1<b$$ Nor anything of the sort that we can take advantage of. Therefore we can't complete our proof with induction. That doesn't mean the statementstatement is false, just that we haven't been able to prove it.

To show it is false, it suffices to find a counter example, and we have plenty of those.

Kevin
  • 567