Proof, Mathematical Induction concept

Question

My prof. just taught us the method of mathematical induction today, and I'm still a little confused on the "Basis step" of the induction procedure.

Why do we have to first prove that p(1) is true, if $p(n) = 3 \mid(n^4 - n^2)$, for all $n \in \mathbb N$ for example.

doesn't the inductive step: " $3|(n^4 - n^2)$ implies $3|((n+1)^4 - (n+1)^2)$ " already a step that proves $3|(n^4 - n^2)$ is true for all $n \in \mathbb N$? Which includes "$n=1$", if the inductive hypothesis is true (AKA we assume the antecedent is true).

According to my guess, I think that we have to start somewhere and show that the initial value is true, then we can continue the inductive step? However, the Basis step is not a necessary requirement in the proof?

Thanks

Answer 1

It is necessary. Here is a slightly different example.

Prove that $n=n+1$ for all $n \in \mathbb N$. Suppose that the statement is true for all $k \leq n$. Then $(n+1)+1=(n)+1$, as desired.

The point is that without the base case, we can prove things vacuously true by using false assumptions.

For your case, you show it is true for $n=1$, then the induction step will show if it is true for $n$, then it is strue for $n+1$. This will guarantee the result for all $n \in \mathbb N$.

The latter half says $P(n) \implies P(n+1)$.

So, if you have the latter half, then you have that $P(1) \implies P(2)$. However, if you have $P(1) \land (P_1 \implies P_2)$, then we can deduce $P(2)$, and so on.

Answer 2

It appears you have not gotten deeply into your chosen example. The more natural induction method is to check that $3|(n^4 - n^2)$ for $n=1,2,3$ and then induction step $n \Longrightarrow n+3$

Answer 3

Think of an inductive proof like a stair case. The inductive step proves "If I am on the 'n-th' step then I can step up to the 'n+1th' step". The basis step says "I can get onto the first step". There can be cases where you could have a working induction however there isn't any basis.

Answer 4

Suppose, you want to prove

$P(k)=0.5+k$ is always an integer, if $k \in \mathbb N$.

If you assume it to be true for some value of $k$, it's very easy to prove that this holds true for $k+1$ too. But this is in fact wrong, obviously.

So what are we missing here?

The base case.

---

To climb a ladder the first thing is, we need to know how to climb on the first step.

I hope you understand now.

Answer 5

In the inductive step, you are proving that $p(n)\implies p(n+1)$. I.e., knowing $p(n)$ is true allows you to conclude that $p(n+1)$ is true. Thus, if we can show $p(1)$ is true, we can use the inductive step to conclude that $p(2)$ is true. Then, we can use the inductive step again to conclude that $p(3)$ is true, and so on. Think of it like climbing a ladder. If we can put our feet on a rung of the ladder, the inductive step tells us that we can take a step up. If we don't prove that $p(1)$ is true in the first place, we have no starting point. I.e., we can't step on the ladder to begin with.

Answer 6

The induction step proves that if it is ever true, it will be true for all the rest. But it does not prove it is ever true in the first place.

How is a silly example but I want to prove that no natural numbers are actually integers.

Induction step: Assume we know that $n\in \mathbb N$ is not an integer.

$n = (n+1) -1$ and $1 \in \mathbb Z$. The integers are closed under substraction so $n+1 \in \mathbb Z \implies (n+ 1)-1 = n \in \mathbb Z$ which we know is not true. Therefore $n+1$ is not an integer.

We have proven $n$ not an integer implies $n+1$ is not an integer, therefore no natural number is an integer.

What is wrong with that proof?

Well, it should be obvious. Our assumption in the induction step simply wasn't true and we had no reason to think it was. So for our proof to be valid we must have at least one base case where we verify our proposition is true.

And we failed to do that.

A less trivial example is that all odd numbers are even.

Induction step. Assume that $2n + 1$ is an odd number that is even so $2n + 1 = 2k$ for some $k$.

Then the next odd number is $2(n+ 1) + 1 = 2n + 2+ 1 = 2k + 2 = 2(k+1)$ and that is even.

So all odd numbers are even. That induction step is valid. But we can not verify that the very first odd number $2*0 + 1$ is even. $2*0 + 1 = 1 \ne 2k$. So our proof fails.

It never actually even starts.