How many cases do I need for a proof by induction

Question

First of all, English is not my mother tongue so I'm sorry if my definitions or concepts aren't explained correctly.

I just started a discrete math course and we started with induction, the professor told us to start taking several specific numbers as cases to see if the hypothesis was right and if all those cases matched the hypothesis we could generalize that property for all the others cases that we didn't use. My question is how do I know how many cases are necessary. For example, let's say I have some property "P" that only works from 0 to 45million, from 45million to 47million doesn't work and then from 47million to infinite it works.

So.. if the cases I used were from 0 to 200 and because all of them matched the hypothesis how can I be 100% sure that It would work for every other number? Is possible that such property could exist? And if so how can I know if certain property works like that?

Answer 1

When you think of induction, one of the best analogies to think about is a ladder. When you climb up the ladder, you have to step on the lower step and need to go up based on it. After we climb up the several steps, we can go up further by assuming that the step you are stepping on exists. Proof by induction works on a similar principle. First, we prove a given statement for a base case that is any natural number $n_0$, this is the lowest step of the ladder. Now we prove that whenever the statement is true for a natural number $k$ then it will be also true for $k+1$. This is same as assuming that if the next step exists then we can climb the ladder. Now from these two parts our statement becomes true $\forall n\in\mathbb{N}, n\geq n_0$.

Answer 2

The few cases that you initially try don't prove the theorem—they show you what the pattern might be. Then, when you think you know the pattern, you express it as a theorem and use proof by induction to show that it's true.

The idea is:

First you show "If this is true for $n=k$, then it is also true for $n=k+1$", without specifying a value for $k$.

Then you apply this to a case you already know to be true (typically the one for $n=1$ or 0) and effectively say "Since this case is true, so is the next one, and the next, and the next, and the next, all the way up to infinity". This is usually worded something like "But this is true for $n=1$. Therefore, by induction, it is true for all $n \ge 1$."

Note that having $k$ as a separate symbol from $n$ makes things a lot less confusing than trying to prove "if it's true for $n$, it's true for $n+1$", since you can be consistent about what $n$ is rather than having to remember what you're currently doing to it, at least in my experience.