Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Here is the picture of the page of the book, I am reading:

enter image description here

$$P_k: \qquad 1+3+5+\dots+(2k-1)=k^2$$ Now we want to show that this assumption implies that $P_{k+1}$ is also a true statement: $$P_{k+1}: \qquad 1+3+5+\dots+(2k-1)+(2k+1)=(k+1)^2.$$ Since we have assumed that $P_k$ is true, we can perform operations on this equation. Note that the left side of $P_{k+1}$ is the left side of $P_k$ plus $(2k+1)$. So we start by adding $(2k+1)$ to both sides of $P_k$: \begin{align*} 1+3+\dots+(2k-1) &= k^2 &P_k\\ 1+3+\dots+(2k-1)+(2k+1) &= k^2+(2k+1) &\text{Add $(2k+1)$ to both sides.} \end{align*} Factoring the right side of this equation, we have $$1+3+\dots+(2k-1)+(2k+1) =(k+1)^2 \qquad P_{k+1}$$ But this last equation is $P_{k+1}$. Thus, we have started with $P_k$, the statement we assumed true, and performed valid operations to produce $P_{k+1}$, the statement we want to be true. In other words, we have shown that if $P_k$ is true, then $P_{k+1}$ is also true. Since both conditions in Theorem 1 are satisfied, $P_n$ is true for all positive integers $n$.

In the top line there is written that we have to show that 'the assumption $P_k$ is true implies $P_{k+1}$ is true'.

And what I think is that: as long as we know that the state of a proposition being true for any positive integer $k$ after Base number implies that proposition is true for integer $k+1$, we have to show that $P_k$ is true. However I don't have an idea yet how to show the truth of $P_k$.

So, my first question is that who is right? My book or me? And if I am right then how can I show the truth of $P_k$?

2) This may be taken as the second question but it is also bit annoying.

In the second paragraph it is written, "Since we have assumed that $P_k$ is true, we can perform operations on it".

Why is it necessary for an equation to be true for performing operations on it? Well, this is not much annoying as compared to the first question because whole the induction theory depends upon that.

share|cite|improve this question
1  
Who is right about what? You haven't made a claim that contradicts the book, – Thomas Andrews Feb 8 at 13:32
2  
I have tried to retype the text from your picture. It would be rather difficult task, considering the low quality of the image. Luckily Google and Google Books returns some places with the same text. Could you perhaps add to your post a more precise reference than "the book I am reading"? – Martin Sleziak Feb 8 at 16:27
1  
You prove the $P_1$ is true. We don't know that $P_n$ is true for all $n$. Only that it is true for $n = 1$. Then we prove that IF it is true for a specific $P_k$ then it is true for $P_{k+1}$. Once we prove these two things: 1) $P_1$ is true. and 2) $P_k \implies P_{k+1}$. Then we can conclude and we have proven 3) $P_n$ is true for all n. Your comment. If we prove it is true for all $P_k$ then it is true for $P_{k+1}$ is irrelevant as we are not assuming and certainly haven't proven it is true for all $P_k$. We have assumed it for ONE $P_k$. – fleablood Feb 8 at 17:25
1  
@MarkJoshi Induction works on many structures. Induction of the form "start at zero and add one" also works on finite fields, that is arithmetic $\pmod p$. It is not correct at all to say that natural numbers are precisely the set for which induction works. – DanielV Feb 9 at 6:02
2  
Once there is enough evidence to make you believe something is true, it can suddenly become much easier to understand why it is true. Given the multitude of experts here (and the authoer himself) telling you the book is right I recommend, as strange as it sounds, to reread the chapter on induction trying to believe it (and everyone on this site) is right and understand why that is, rather than trying to argue why it is wrong. – Bananach Feb 9 at 13:25
up vote 8 down vote accepted

Your book is right. You have to show that $$P_k \implies P_{k+1}$$

Because if you prove that and since you said it is true for base number, the proposition is automatically proved true for every $n \in S$.

Let us see how!

To prove "$P_k \implies P_{k+1}$" means you are proving that a particular proposition has a quality of being true for $k+1$ because of being true for $k$.

Improvement (Edit): Just as you do in case of domino effect. Suppose it is reported that the cornered domino has been pushed over. And then you find out that dominoes are arranged such that whenever $k^{th}$ domino falls, $(k+1)^{th}$ falls. You would at once say that all dominoes must fall.

Remember that these two conditions of induction theorem simultaneously imply that a certain proposition is true.

i) It is true for base number

ii) It is true for an integer $k$ implies it is true for integer $k+1$ after it.

For the proposition in your picture, if you would take base number $2$ then after doing all that (done in your book), you would prove that proposition is true for integer $2$ and integers after it. But since we usually ask to prove that conjecture for every $n \in \mathbb N$, we take base number $1$ not $2$ because the smallest number of set $\mathbb N$ is $1$.

share|cite|improve this answer
3  
It may help to think that you are supposed to prove the arrow in-between the two propositions. – anktastic Feb 9 at 4:00

Induction is, intuitively, an outline of an infinite proof.

You first prove $P(0)$, the base case.

Then you prove $P(1)$ follows from $P(0)$.

Then you prove that $P(2)$ follows from $P(1)$.

Et cetera.

In general, if you know that $P(k+1)$ follows from $P(k)$, and you know that $P(0)$ is true, then you know how to prove $P(n)$ for any natural number. For example, $P(4)$ follow because $P(0)\implies P(1)\implies P(2)\implies P(3)\implies P(4)$.

So you don't need to know how to show $P(k)$ to show that $P(k)$ implies $P(k+1)$. Once you've shown this implication, and $P(0)$, we know how to write a non-inductive finite proof of $P(10000)$ or $P(10^{99})$.

share|cite|improve this answer

(Wanted to post as a comment, but it is too long :/)

When we prove something by induction we prove that our claim is correct for a base case (for example, n=1). Afterwards we assume (not proving, only assuming) that our claim stands for some arbitrary value k and than, based on the assumption we prove it holds for k+1.

Note that based on the proof of base case and the proof that if $P_k$ is true we show that $P_{k+1}$ is true. Example: you prove that some claim is correct for $n=1$, then you assume it is correct for some n=k. Now you prove for n=k+1.

We proved for n=1 and using the assumption that the claim stands for n=k we proved for n=k+1. In this case, we know that the claim stands for n=1, thus we can now say it stands for n=2. Afterwards we can say that it stands for n=3 and so on, hence it stands for any n.

That is how we use induction - you don't prove that $P_k$ is true, you assume it it true - that is a big difference.

If my explanation is not coherent enough, you might want to google "Induction" and read a little more.

Good luck.

share|cite|improve this answer
    
"...that our claim stands for some arbitrary $k$ and then, based on the assumption we prove that claim holds for $k+1$" . Okay.. if we prove the claim for $k+1$ . At what place in the picture, I can see such prove? – Man_Of_Wisdom Feb 8 at 14:12
    
All that shown is how they are assuming that $P_k$ is true and how they use it to prove that $P_{k+1}$ is true. – Galc127 Feb 8 at 14:23
    
After reading this "$P_k$ holds implies $P_{k+1}$ holds", I guess that we should show truth of $P_k$ and not of $P_{k+1}$ because it is an implication and once we prove $P_k$, then according to our claim ($P_k \implies P_{k+1}$), $P_{k+1}$ would get proved automatically. – Man_Of_Wisdom Feb 8 at 14:30
    
@Man_Of_Wisdom, the induction assumption is that $P_k$ is true, we don't need to prove it. We show that because it is true (take it as a fact), than $P_{k+1}$ is also true. We know that "$P_k$ holds", we want to show that $P_{k+1}$ holds. – Galc127 Feb 8 at 14:43
2  
You show the truth of $P_1$. Than you show that if it's true for $P_k$ which may or may not be the same as $P_1$ then it must be true for $P_{k+1}$. From that we know that $P_1 \implies P_2$. And therefore $P_2 \implies P_3$. Now we can hire an undergraduate to sit in an office to continue "$...\implies P_{2,345}$ and $P_{2,345} \implies P_{2,346}$ and $P_{2346} \implies ...$". Or we can conclude: 1) ($P_1$ is true). and 2) ($P_k \implies P_{k+1}): \implies $ 3) $P_n$ is true for all $n$. – fleablood Feb 8 at 17:31

What do we actually prove using induction theorem?

Probably an example is needed here. Let's suppose you want to prove the little Gauss. Suppose we want to prove this Theorem for all $n\in\mathbb{N}$:

$$ 1+2+3+ \cdots+ n = \sum_{k=1}^n k = \frac{n(n+1)}{2}$$

The statement $A(n)$ is thus given by: $$ \sum_{k=1}^n k = \frac{n(n+1)}{2} $$ With induction this is really simple. Step one lets suppose $n=1$: $$ 1 = \sum_{k=1}^1 k = \frac{1(1+1)}{2} = \frac{n(n+1)}{2} $$ Done the statement is true for $n=1$. The good part about induction is we can select the number for which we want to prove it so we could also have shown with $n=0$. So dont try to prove it for $n$ beeing any number but prove it for one number you selected, almost everytime $n=0$ or $n=1$.

Now we have to prove that if the statement is true for $n$ it is also true for $n+1$. Meaning if $A(n)$ is true, $A(n+1)$ is also true:

$$ \underbrace{1+ 2+ \cdots + n}_{\sum_{k=1}^n k} + n+1 = \sum_{k=1}^n k + n+1 \overset{A(n) \text{ is true}}{=} \frac{n(n+1)}{2} + n+1 = \frac{n^2+n+2n+2}{2} = \frac{n^2+3n+2}{2} = \frac{(n+1)(n+2)}{2} $$

So now we know the statement is true for $n+1$ or $A(n+1)$ is true.

Prove without induction

Proving this statement without induction is not that simple. You can do it like this. Suppose $n\in \mathbb{N}$, then we can look at the sum and rearange that:

$n$ is even

$$ 1+2+\cdots + n = (1 + n) + (2+n-1) + \cdots + \left(\frac{n}{2} + \frac{n}{2} +1\right)=\frac{n}{2}(n+1) = \frac{n(n+1)}{2} $$

and for $n$ is odd

$$ 1+2+\cdots + n = (1+n) + (2+n-1) + \cdots + \left(\frac{n-1}{2} + \frac{n+1}{2} + 1\right) + \frac{n+1}{2} = (n+1)\frac{n-1}{2} + \frac{n+1}{2} = \frac{n(n+1)}{2}$$

Conclusion

So let's conclude, we can use induction here but we can go without it too. The first though is much simpler because it uses the induction and if you get your head around it, it's easier to verify that it is true. The other one is using induction internally for the rearanging and you have to think alot if this is true or if I made a mistake.

What does the operation part mean?

The funny thing is that induction can be generalized in a lot of things. If we look at the set $\mathbb{N}$ than we can define it as follows $1$ is in $\mathbb{N}$ and if $n\in\mathbb{N}$ than $n+1$ is also in $\mathbb{N}$, meaning lets call that $(\star)$:

  1. $1 \in \mathbb{N}$
  2. $\forall n\in\mathbb{N} \Rightarrow n+1\in\mathbb{N}$

If you look at that you will find this is looking a lot like induction. So basically you can say if you have the statement $A(n)$ and you want to show that it is true for all $n\in\mathbb{N}$ you do the following, you determine the set $\mathfrak{A}$ for which the statement is true. This set is given by: $$\mathfrak{A} = \{n\in\mathbb{N} | A(n) \text{ is true}\}$$ And now if we know $1\in\mathfrak{A}$ and for all $n\in\mathfrak{A}$ it follows $n+1\in\mathfrak{A}$ then it follows from $(\star)$: $$ \mathfrak{A} = \mathbb{N} $$ so the statement is true for all $n\in\mathbb{N}$

More generalized induction shemes

The example where this is generalized is the "principle of the good set" (this is the german name translated directly), it's used in measure theory and works with sets that are way bigger then $\mathbb{N}$ in fact with sets that have the cardinality of $\mathbb{R}$. And it works as follows. A $\sigma$-Algebra $\mathcal{A}$ of a set $\Omega$ fullfills the following axioms:

  1. $ \Omega \in \mathcal{A} $
  2. $ A\in \mathcal{A} \Rightarrow \Omega\setminus A\in\mathcal{A}$
  3. $ A_1,A_2,\cdots \in \mathcal{A} \Rightarrow \bigcup_{k=1}^\infty A_k \in \mathcal{A}$

Now we have a function $\sigma$ that generates $\sigma$-Algebras for a given subset $\mathcal{G}\subset \mathscr{P}(\Omega)$ just using the axioms 1-3 just more often than $\mathbb{R}$ has elements. Like $\mathbb{N}$ is generated by $\{1\}$, if we take $1$ and then we add $1$ onto it put the result $2$ in our set. Then we take $2$ and add $1$ onto it and put it in our set until we cannot add any more element because we have all of them already. Back to the example, $\mathcal{G}$ is called a generator if $\sigma(\mathcal{G}) = \mathcal{A}$, this also means $\Omega \in \mathcal{G}$. Now if we want to show a statement $B(A)$ is true for all $A\in\mathcal{A}$ we just show:

  1. $B(G)$ is true for all $ G\in \mathcal{G}$
  2. $B(A)$ is true then it is also true for $ B(\Omega\setminus A)$
  3. $B(A_1),\ B(A_2),\ \cdots$ is true than its also true for $B\left(\bigcup_{k=1}^\infty A_k\right)$

So here 1. shows that we know the statement is true for at least a generating set of $\mathcal{A}$, like in induction we know the statement is true for $\{1\}$ which generates $\mathbb{N}$ using $n+1$. And then we show it for the operations 2. and 3. like we would in induction where we show it for $n+1$.

Conclusion

I hope I didn't confuse you too much. But I am certain that after some time you will accept inductions and learn how to use them. And if you once return here or have to explain it to somebody else, after using it a lot of times. You will fully understand it. People often find induction counter-intuitiv, I have some ideas why but I think that would really go to far. So my hint, accept it first, use it, try to explain it und you will have understood this and similar shemes.

share|cite|improve this answer

Intuitively you can view this as a chain reaction, because once you show that $\color{green}{P_0}$ is true, then by applying $\color{blue}{P_k \Rightarrow P_{k+1}}$ repeatedly you can reach any number $n \geq 0$ and see that $P_n$ is indeed true.

$$\color{green}{P_0} \color{blue}{\Rightarrow} P_1 \color{blue}{\Rightarrow} \dots \color{blue}{\Rightarrow} P_n \color{blue}{\Rightarrow} \dots . $$

At no point are you directly proving that $P_1$, $P_2$, $\dots$ are true, instead they follow from base case and induction step.

share|cite|improve this answer
    
What is $P_k \implies P_{k+1}$? I think my question actually asks about this. – Man_Of_Wisdom Feb 8 at 14:17
1  
It is the implication, you are proving $P_{k+1}$ under assumption of $P_{k}$, i.e. you are assuming that $P_{k}$ is true, and you show that then $P_{k+1}$ is true. Once you prove that, you can apply this for case $k=0$ (because you know that $P_0$ is true). By that you immediately get that $P_1$ is true. And you can repeat that... – Sil Feb 8 at 14:20
1  
You must combine it with the base case, in which you proved that $P_0$ is true. Both base case AND induction step then imply that $P_1$ is true. But now you have $P_1$ is true and you can use it same way with induction step, to arrive at $P_2$ being true, etc... Reaching any $n$ if you repeat the process. – Sil Feb 8 at 14:25
1  
And that is exactly what you do, in case of $P_0$. You have $P_0$ and $P_0 \implies P_1$, therefore $P_1$. The trick is that you ONLY need to show this for $P_0$, everything else follows from the $P_k \implies P_{k+1}$. – Sil Feb 8 at 14:48
1  
You prove $P_k$ is true when $k = 1$. You do not need to assume that $k \ne 1$ or that $P_k$ is true for any value of $k$ other than 1. But you don't want to assume that $k$ has any characteristic that pertains only to 1. You want to prove that it is true for some $k$ of which you don't know the value of, then it must also be true of $k + 1$. You know it is true for some $k$ because it is true for $k = 1$. It might also be true for $k = 7,921$ but you don't know that. You can't say I know it is true for $P_1$ so I will prove it for $P_2$ because you want something more general. – fleablood Feb 8 at 17:39

The part about assuming $P_k$ is an application of basic rules of propositional logic.

Suppose you have a proposition of the form $A \implies B$. One way you might be able to prove this proposition is by using the rule for Introduction of an Implication:

  1. Assume that $A$ is true.
  2. Using $A$ as a statement already known to be true, prove $B$.
  3. "Discharge" the assumption that $A$ is true.
  4. Conclude that $A \implies B$ is true.

Of course this works only if you are able to come up with a proof of $B$ in the context of Step 2. But while you are in that context, you already know $A$ is true, and you do not have to prove it.

Once you have proven $A \implies B$, if you later find out that $A$ actually is true (not just assumed to be true in the limited context of Step 2, above), you can apply a rule called Modus Ponens:

  1. Given that $A \implies B$ is known to be true.
  2. Given that $A$ is known to be true.
  3. Conclude that $B$ is true.

None of these rules of logic has used anything from the method of induction, but the method of induction uses those rules of logic.

We prove $P_0$.

We prove $P_k \implies P_{k+1}$ for any possible value of $k$, using the rule for Introduction of an Implication.

Now we know $P_0$, and since $P_k \implies P_{k+1}$ for any $k$, including the case $k=0$, we have $P_0 \implies P_1$. Apply Modus Ponens:

  1. Given that $P_0 \implies P_1$ is true.
  2. Given that $P_0$ is true.
  3. Conclude that $P_1$ is true.

Now we know $P_1$, and $P_k \implies P_{k+1}$ is still true in the case $k=1$, so we can apply Modus Ponens again:

  1. Given that $P_1 \implies P_2$ is true.
  2. Given that $P_1$ is true.
  3. Conclude that $P_2$ is true.

We can repeat this process as many times as needed to show $P_3$, then $P_4$, then $P_5$.

The principle of induction merely summarizes this long, repetitive, boring process so that we can relatively quickly show $P_n$ for any given non-negative integer $n$. And since we can always do this no matter what non-negative value we choose for $n$, we conclude $P_n$ is true for all $n$.


By the way, I would write at least one of the sentences in the book a little differently. Instead of "perform operations on this equation" I would write "use algebraic manipulation of $P_k$ to prove that other equations are true". That is,

Since we have assumed that $P_k$ is true, we can use algebraic manipulation of $P_k$ to prove that other equations are true.

I hope this clears up one of the points of confusion.

share|cite|improve this answer
    
According to point no. 2 we have to prove that $P_{k+1}$ is true based on the assumption that $P_k$ is true. The author shows us that $$P_{k}+T_{k+1}=P_{k+1}$$. Is it the way to implement point no.2? And, if it iss then how? I mean in what way proving $P_{k}+T_{k+1}=P_{k+1}$ is equivalent to proving $P_{k+1}$ under the assumption?? – Man_Of_Wisdom Feb 9 at 10:41
    
What does $P_k + T_{p+1}$ mean? $P_k$ is an equation. Does it make sense to write $(5^2 = 25) + 3$? I would never write math that way. But do you agree that if $a$ and $b$ are numbers and $a=b$, then $a$ and $b$ are the same number, so $a + 3$ is the same as $b +3$, that is, $a+3=b+3$? That's what we mean by "add ___ to both sides of the equation." And yes, when you start with a true equation, then (the left side plus something) is equal to (the right side plus the same something), which is how the author derived $P_{k+1}$. – David K Feb 9 at 12:52
    
DavidK first of all, adding something to an equation always means it is added to its both sides. In other words, it can never mean to add something to only side of equation because two sides make up an equation. So $P_k+T_{k+1}$ is not wrong anyway. It is not necessary for something to be right. When it is only "not wrong", we can adopt it. – Man_Of_Wisdom Feb 9 at 18:41
    
Secondly, you said that since we assumed $P_k$ is true, we add $T_{k+1}$ to its both sides and then if it becomes $P_{k+1}$, it is proved that $P_{k+1}$ is true. And to support it, you said that if something is added to a true equation such as $3^{2}=9$ then the new equation for example $3^{2}-1=9-1$ is necessarily true (because it is the property of equation). In case of $3^{2}=9$ we are certain that the equation is true but in case of $P_k$ we are at the sake of assumption. These two things are different. I am sure I am missing something but please explain more accurately. – Man_Of_Wisdom Feb 9 at 18:54
    
On the second point, that's the whole point of Introduction of an Implication. To prove $P\implies Q$, assume $P$ is true and show that $Q$ is true under this assumption. Of course now all you have actually shown is that $Q$ is true if $P$ is true; but that is what $P\implies Q$ means. – David K Feb 9 at 19:09

"as long as we know that the state of a proposition being true for any positive integer k after Base number implies that proposition is true for integer k+1, we have to show that Pk is true. "

1) No, you don't. If I wanted to show that IF Godzilla were 10 times as large in all dimensions as a T. Rex THEN Godzilla would be weigh 1,000 times as much, I do NOT need to prove that Godzilla is 10 times as large in all dimensions as a T. Rex. I CAN'T prove Godzilla is 10 times as large in all dimensions as a T. Rex because Godzilla isnt 10 times as large in all dimensions as a T. Rex.

and

2) You already have shown $P_k$ is true for some k. You have shown it is true for $k = 1$. Reread that statement. It does not say "we will assume this is true for all $P_k$ and show that means it is true for all $P_{k+1}$". It says "we will show that if it is true for (one) $P_k$ than that means it is true for $P_{k+1}$".

Thus we have proven an infinite loop: If it is true for k, then it is true for k + 1: Relabel k+1 as k and it is true for k + 1 (which is the old k + 2): Relabel and repeat indefinitely and we have proven it is true for all $n \ge k$. Now we just need to demonstrate that it is true for a single base case k. Oh, wait. It's true for k = 1. Therefore it is true for $n \ge 1$.

As for you second question....

"Why is it necessary for an equation to be true for performing operations on it?"

It isn't. You can perform operations on untrue equations. You just can't assume any of the results are true.

Let me write down: "2 + 2 = 5". Let me perform operations on them:

$7^{2+2} - 37*5 = 7^5 - 37*{2 + 2}$

$2401 - 185 = 16,807 - 74 -74$

$2,216=16,659$

I can do that. But I can't get any meaningful results.

====

In a very abstract and philosophical way a proof by induction is a tiny bit like a proof by contradiction.

In both you assume a statement without proof and you reach a conclusion that would be true if your assumption were.

In a proof by induction you might prove that following: "If any even number is divisible by two then they all are divisible by two."

And in a proof by contradiction you might prove the following: "If any odd number is divisible by two then they all are divisible by two."

What's the difference in these statements? They are both shown in the exact same way ("if $2|n$ then $2|n + 2$ and $2|n - 2$"). They are both equally valid. And furthermore, they are both TRUE.

But in the proof by induction you verify a single confirmation: "2 is divisible by two. Therefore all even numbers are."

While in a proof by contradiction you contradict with a contradiction: "3 is not divisible by two. Therefore no odd numbers are."

share|cite|improve this answer

There is another way of thinking of this.

Throw out the standard induction theorem, and replace it with this one:

Any nonempty set of natural numbers has a smallest element.

This seems obviously true, right? This is called the well-ordering principle, and it is equivalent to induction. Here's how you do induction with the well-ordering principle (WOP for short):

  1. Prove that $P_0$ holds (or $P_1$, if you don't consider zero to be a "natural number").
  2. Take this set: $$ S = \{x | x \in \mathbb{N} \wedge \neg P_x \} $$ That's the set of natural numbers for which our proposition does not hold.
  3. Assume $S$ is non-empty. Then, by WOP, it has a least element, which we can call $k+1$. In particular, we know that $\neg P_{k+1}$ (we know that the proposition does not hold for $k+1$, since it's an element of $S$).
  4. By step (1), we know $k+1 > 0$ (or $k+1 > 1$, if you started with $P_1$). So $k$ is a natural number. If we had not proven step (1), $k$ could be equal to negative one (or zero), which would invalidate the rest of the proof.
  5. Prove that $\neg P_{k}$; that is, prove that the proposition is not true for $k$, based on our knowledge that it is not true for $k+1$.
  6. Since $k < k + 1$ and $k \in S$, we have a contradiction ($k + 1$ isn't the smallest element of the set). That means our assumption in step (3) must be false. The set of counterexamples is empty, meaning the proposition must hold for every number.

Note that these statements are equivalent: $$ P_k \implies P_{k+1} \\ \neg P_{k+1} \implies \neg P_k $$ If you can prove one, you can prove the other quite easily. Standard induction asks you to prove the first, while WOP-based induction requires you to prove the second.

In the end, it's just a matter of notation. But you might find one form of induction more intuitive than the other. If you are going to use this method, you should note that we usually talk about $k$ and $k - 1$ instead of $k+1$ and $k$; I used the latter because it corresponds more obviously to standard induction.

share|cite|improve this answer

Think about Peano system (see footnotes) for defining natural numbers. You take an initial number, which you call 1, and then you say:

  • Element 1 exists in the set.
  • Any successor of an element n in the set, say $suc(n)$, exists in the set.

With these axioms, you construct the whole set of natural numbers. You don't need to prove such elements exist in a deductive was as you think, but you must construct the proof and you have the building blocks for that (while in the deductive method, the path is the inverse).

So, the analogous of Peano system applies for the induction:

  • Prove that $P(1)$ exists, where 1 is just the base case you want to start the proof with. This is the equivalent of the Peano system for the value 1.
  • The constructive step: Prove that $P(n+1)$ is true when $P(n)$ was true. In this case, you move forward in the demonstration (induction actually means move towards the end) to construct the successive cases in the proof.

So you initially prove $P(1)$. If you prove $P(n) => P(n+1)$ then you can start traversing infinitely:

  • $P(2) because P(1)$
  • $P(3) because P(2)$
  • ...

You never prove the $n$ case, because $P(n)$ is in hypotetic case which derives ultimately from the case $P(1)$, and formerly being $P(n)$, it was $P(n+1)$ in former... iterations.

So, the way to think why you should assume $P(n)$ is true, is because:

  • In an initial case, $P(1)$ has been proven true by you. If you didn't, then you should start for it.
  • Since the construction is upward, instead of downward, you should not think that you have to prove the n-case, but that you have alreadr proven it.

Footnotes:

  • You are not forced to start from 1 and upwards. You can take any number you want, and so you will restrict the proof on it and further.
  • Other induction processes can traverse entire integer set instead of just natural numbers. Such proof system involves prooving $n+1$ and $n-1$.
share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.