a problem with the induction hypothesis

Question

I have used mathematical induction in a lot of excercices but I still feel like I am missing something important and that I am only manipulating formulas. Maybe there's also a language issue because English isn't my first language.

If I read[1] "if the statement holds for some $n \in \mathbb{N}$" does this mean that I suppose that there exists a certain $n \in \mathbb{N}$ such that the statement is true or that I suppose that the statement is true for an arbitrary $n \in \mathbb{N}$? I am confused because neither of these possibilites seems satisfying to me.

On the one hand, if there only exists a certain $n$ for which the statement holds, I cannot infer that the statement holds for smaller integers. On the other hand, if I suppose that the statement is true for an arbitrary $n \in \mathbb{N}$, am I not supposing what I want to prove in the end?

What I would expect is something like this: "if the statement holds for all $m \leq n$". Here[2] is a proof of the fundmental theorem of arithmetic where induction is used this way: "By induction: assume it is true for all numbers between $1$ and $n$". This appeals nicely to my intuition but it is clearly not the way induction is usually applied.

Does somebody understand my line of thought and my confusion and can help me to clear it up?

[1] https://en.wikipedia.org/wiki/Mathematical_induction#Description (I don't have access to a maths book at the moment)
[2] https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic#Proof

Answer 1

The induction hypothesis DOES suppose the statement is true for some $n \in \mathbb{N}$. However this does not assume what you are trying to prove because you will prove that the statement $P$ is true for some "base case".

The proof method is:

1) Base case: Prove P(0) (say) holds. That is $P$ holds for $n=0$

2) Induction hypothesis: Assume P(n) holds for arbitrary $n \in \mathbb{N}$ --- Which is okay, I mean not cheating, because we have shown that it is true for $n=0$

3) Prove, using the induction hypothesis, that p(n+1) holds.

So in the end you will have proven $P(0)$ holds, and if $P(n)$ holds for some $n$ (which it does, $n=0$) then $P(n+1)$ holds.

In conclusion $P(0)$ is true, thus $P(0+1) = P(1)$ is true, thus $P(2)$ is true... so on and so forth

I hope this helps :)

Note: Base case is dictated by the question, it may not be $n=0$. But you just need to prove it holds somewhere and then you will be able to conclude it holds for all numbers AFTER that.

Answer 2

Perhaps it is enlightening to consider induction as a two step proof, consisting of two proofs. Reversing the usual order, we prove 1) the so called "inductive hypothesis"; 2) the base case.

1) is just the proof of "For all $n$, if $p(n)$ is true, then $p(n+1)$ is true."

2) is the proof of "$p(m)$ is true" for some particular integer $m$.

After proving 1) and 2) independently of each other, we combine them with 3) The principle of mathematical induction, which asserts that whenever both 1) and 2) hold that $p(n)$ is true for all $n\geq m$.