What do we actually prove using induction theorem?

Question

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

$$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.

Answer 1

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$.

Answer 2

(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.

Answer 3

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})$.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

"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."

Answer 8

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$.

Answer 9

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.