I have no idea how proving shit works in maths, and I've basically spent the last week in class with a blank face. So if anyone at all can help me make sense of the question (don't solve it outright, give me some pointers), I would gladly appreciate it.

Looks to me like the error is not providing a definition for what "even" actually means. So the initial assumption of n=0 being even is flawed because you haven't even set up the base condition. (Depending on how pedantic you want to be with the proof).

Beyond that, the error is the assumption that because a claim is true for a single number in a series, it applies to every number in that series. So for this problem it'd be in step 2 of the Base Case section. It's further messed up by step 3, because you're using an assumed value (n=1) to perform actions, rather than a true value to perform actions. However step 3 is a "valid" step, in that its logic is fine, the issue with step 3 is the premise.


Alternatively, you can say "I have many glorious (dis)proofs for this problem, the margins of which this paper is too narrow to contain." You'll probably get the problem wrong, but you'll definitely get points for style.

"By assumption, both 1 and k are even numbers" <.<

The assumption is wrong ("Assume that..."). From a false assumption you can prove false statements by logically correct arguments.

More concretely, proof by induction works by first proving that some first statement is true and then showing that if the nth statement is true, the (n+1)th statement is also true. Therefore if the first statement is true, so is the second one etc. There is a crucial step missing in the "proof" by induction given in the problem.

Actually, the mistake here runs deeper than just the bogus assumption that 1 is even.

The method to be employed here is strong induction (the emphasis is intentional: this is a particular style of proof by induction).

In proof by strong induction, it is good form to assume "all N less than or equal to K". And it can be shown that all proofs by strong induction are equivalent to similar proofs by ordinary induction. The choice of which method to use is merely a choice of convenience.

The actual error is so obscure that I will give it even though the OP just wanted a pointer to it. It is the unstated assumption "K > 0".

The working out of why this unstated assumption is both a sufficient and a complete explanation of the false "proof" is left to the OP :)

I agree with your logic, but I'm 99% sure that that's not what they were asking for. Also, where I'm from the notation n = 0, 1, 2, ... , k implies that k > 0.

Hang on, so if n = 0, 1, 2, 3... and if k+1 = n, and if we were to say k+1 = 1, then that would be a contradiction since k > 0. Is that how it works? Moreoever, why is it k > 0? Why wouldn't it be k > 1 or any other number in n?

In every proof by induction, it is easy, tempting, and incorrect to assume K > N[sub]0[/sub]. This is an essential point in the understanding of correct and incorrect inductions. That's why I pointed to it, and not to the badly written assumption clause.

Writing "n = 0, 1, 2, ..., k" is justified only by that (incorrect) assumption. While it is the visible sign of the proof having gone wrong, it is a mistake that is possible to make only if you have ignored the previous point.

It is especially troublesome in strong induction, as in this case, where the instructor used the assertion that 1 was included in the assumed set, in the proof.

But it is always possible, and only possible, if you have already violated (deliberately or inadvertently) the point I stressed. If you consider only K > N[sub]0[/sub], then the proof must fail.

The proof relies on the unproven assumption that 1 is even.

It's refreshing to see someone write "maths" instead of "math". The word "math" is a pet peeve of mine.

Aren't people going about this too complicatedly?

The underlying assumption that n=k+1 is wrong. It should be n=k+2. The idea that 1 is even is not an assumption, but rather a logical conclusion from the assumption that n=k+1.

If n=k+1 were the case, k=0 and n=even number would logically give n=1 and must therefore be even. It is not an assumption in its own right, but rather an assumption on the part of the author that the reader will be able to determine that.

A mathematical assumption is a subject that cannot be or is not scientifically or logically proven. n=k+1 is only even because the author says it is.

Or am I missing something here?

Edit: Just read the first bit again. n=k+1 is derived from the idea that strong induction is used to determine that n=even and n=0,1,2,3,4,l so therefore logically n=k+1. I'm not much of a mathematician, but strong induction doesn't seem like much of a watertight methodology to me.

So to summarise, a strong induction relies on the fact that the statement made must hold for all values, greater or equal to k. Therefore, in this case, the proof is false because if n includes 0, it would contradict with k since 0+1 = 1, which is not an even number. Is that right?

Assumptions are assumed, not proven; there is no such thing as an unproven assumption, only unjustified ones. Here, the unjustified assumption is that the range includes 1. The only reason it is unjustified is that the case where it does not has been neglected.

In the step part of a strong induction, you must prove "if the proposition is true for all the integers in [N0 .. K], it is true for K + 1."

The mistake is that it does not hold when the only integer in [N0 .. K] is 0.
That's right. I think we have a little difference in notation, but I think you have it.

If you omitted the "or equal", then you would not consider the case where k = 0. But the case where k = 0 is the only place the proof is broken.

That's a pitfall of induction proofs in general, and even more dangerous in strong induction. It's one of the reasons mathematicians distrust induction proofs.

Any assumption that is unproven is an unproven assumption. Of course they exist.

Now, "unproven assumption" isn't an error in itself, but in this case it is where the error lies. This particular "proof" holds only for cases where the assumption is valid, and the conclusion doesn't follow from from the "proof" until this assumption is proven to be valid.

That's just not so, though we are well beyond the OP's original question by now. Induction proofs follow a particular mechanic. They follow only that mechanic. To hold them to a nonexistent stricter standard is itself an error, and raising it invalidates your criticism of the proof.

In the step of an induction, you don't prove -- you don't even question whether the proposition is true for K. The only thing that matters is "if it is true for K, is it true for K + 1?" (in "strong induction", read "if it is true for [N0 .. K], is it true for K + 1")

But if there is some K for which the step fails, then the proof fails. The only K for which the strong inductive "proof" of "all whole numbers are even" fails is K = 0. If it were not for that single case, the "proof" would be correct as written.

In real, important, and interesting problems, the importance of proof by induction is that you never have to prove or even justify the assumed side of the step. This allows you to prove many things that otherwise would be tedious beyond all practicality.