A problem of mathematical induction

[sahilmm15]

I have gone through the principle of mathematical induction. I cannot understand why do we need to prove every statement for n=1. I mean why is it necessary? Why can't we start directly from n=k then n=k+1. For example see the below image. Thanks!

 

[BvU]

If you can prove it for n = k you don't need induction

 

[sahilmm15]

If you can prove it for n = k you don't need induction

Correct me if I am wrong. By seeing the 'domino' analogy we use the base case like p(1) or p(0) to actually 'check' whether the domino in the 'first' place has actually fallen or not. If not then there is no point in proving the statement. If it is true then we can carry with our process of proving the whole statement true.

 

[BvU]

I cannot understand why do we need to prove every statement for n=1

Induction goes like

IF $\Biggl [ \ p(k) \Rightarrow p(k+1)\ \Biggr ]$ AND $\ \ p(1)\ \$ THEN $\ \forall n: \ \ p(n)$

so you don't prove $p(k)$ but only prove that IF p(k) THEN p(k+1)

 

[Office_Shredder]

Correct me if I am wrong. By seeing the 'domino' analogy we use the base case like p(1) or p(0) to actually 'check' whether the domino in the 'first' place has actually fallen or not. If not then there is no point in proving the statement. If it is true then we can carry with our process of proving the whole statement true.

This is right. So what's your question?

To see an example at work where the base case is important, take the formula for the sum of squares that's in your example, and add 1 to it. The inductive step will still work just fine.

 

[sahilmm15]

Induction goes like

IF $\Biggl [ \ p(k) \Rightarrow p(k+1)\ \Biggr ]$ AND $\ \ p(1)\ \$ THEN $\ \forall n: \ \ p(n)$

so you don't prove $p(k)$ but only prove that IF p(k) THEN p(k+1)

Thanks I am clear now. I like how this community is so active, they just answer instantaneously. It makes me easier to understand. Thanks again !

 

[Gaussian97]

As a trivial example, consider the statement $n = n + 1$.
Is really easy to prove $p(k) \Longrightarrow p(k+1)$ but that doesn't prove the above statement (which obviously is false), so you can see why we need to prove $p(1)$.

 

[trees and plants]

May i suggest another example like $n^2>\sqrt{n}$ For $n=1$ it is wrong, but trying to prove it without $p(1)$ leads to wrong results for every natural number. The more general statement of mathematical induction where we start from another natural number as a starting point not $1$ is needed i think.

It could be $p(k)$, where $k$ is a natural number for that starting point.

 

[Gaussian97]

Well, if you have some statement $F(n)$ that is not true for $n=1$, but you can prove $F(k)\Longrightarrow F(k+1)$ and you can prove $F(n_0)$ for some $n_0$. Defining a "more general induction" isn't essentially useing induction over the statement
$$G(n) = F(n + n_0 - 1)$$
?

Concretelly, proving $$n^2 > \sqrt{n}, \quad \forall n>1$$
is equivalent to prove the statement $(n+1)^2 > \sqrt{n+1}$ by induction, which can be proved for $n=1$