Question about mathematical induction

[parshyaa]

In mathematical induction we prove statements using a proper technique just like in a following example:
$P(n)=n(n+1)$ is an even number for every $n∈N$

1. we will check wether $P(1)$ is True/false, its true because $P(1)=2$
2. Now We will assume that $P(k)$ is true and using this we will prove that $P(k+1)$ is also true

This is the part I don't get: Assume $P(k)$ is True

We are just assuming something is true and then 'proving' that something else is true based on that assumption. But we never proved the assumption itself is true so it doesn't seem to hold up to me. Oviously proof by induction works so am I viewing the process incorrectly?

 

[SlowThinker]

Lets say you want to verify that P(30) is true.
You proved that P(1) is true.
You proved that if P(1) is true, then P(2) is true.
You proved that if P(2) is true, then P(3) is true.
...
You proved that if P(29) is true, then P(30) is true.
Therefore, P(30) is true.

The important ingredient is that natural numbers are defined in a similar fashion:
A1: 0 is a natural number. (or you can start at 1)
A2: Every natural number has a successor, which is later shown to be X+1 for X.
The proof by induction follows this pattern, so it proves P for all natural numbers.

 

[fresh_42]

In mathematical induction we prove statements using a proper technique just like in a following example:
$P(n)=n(n+1)$ is an even number for every $n∈N$

1. we will check wether $P(1)$ is True/false, its true because $P(1)=2$
2. Now We will assume that $P(k)$ is true and using this we will prove that $P(k+1)$ is also true

This is the part I don't get: Assume $P(k)$ is True

We are just assuming something is true and then 'proving' that something else is true based on that assumption. But we never proved the assumption itself is true so it doesn't seem to hold up to me. Oviously proof by induction works so am I viewing the process incorrectly?

There are basically three ways of looking at it.

1. Formally, it is based on the Peano axiom which guarantees that there is always a following number. I'm not 100% sure as I don't remember a formal deduction from the axioms.
2. Intuitively it is: Let's prove $P(1),P(2),P(3), \ldots$ until it gets boring and we assume we have done it for some number $k$ and see whether it could also be done for the next number.
3. The trick is, that in contrast to simply prove $P(k)$ for any fixed number $k$, which by the way could be easily done in your example, we prove that the previous truth $P(k-1)$ can be used for the step to the next number and thus we can go from number to number as long as we like.

Induction is basically the formalism for: and so on, ... , etc. or similar. It needs an anchor, to be true somewhere, and a step that brings us to the next number.

 

[parshyaa]

Lets say you want to verify that P(30) is true.
You proved that P(1) is true.
You proved that if P(1) is true, then P(2) is true.
You proved that if P(2) is true, then P(3) is true.
...
You proved that if P(29) is true, then P(30) is true.
Therefore, P(30) is true.

The important ingredient is that natural numbers are defined in a similar fashion:
A1: 0 is a natural number. (or you can start at 1)
A2: Every natural number has a successor, which is later shown to be X+1 for X.
The proof by induction follows this pattern, so it proves P for all natural numbers.

This is not what i am asking, i know how MI works but only thing i want to know is how we can be so depended on the Assumption, we didn't proved it, we just assumed it and proved later one

 

[SlowThinker]

This is not what i am asking, i know how MI works but only thing i want to know is how we can be so depended on the Assumption, we didn't proved it, we just assumed it and proved later one

Of course we proved the Assumption. Either in the first, direct step, or in the previous application of the 2nd rule. Look at my post again.

 

[fresh_42]

This is not what i am asking, i know how MI works but only thing i want to know is how we can be so depended on the Assumption, we didn't proved it, we just assumed it and proved later one

But that's what we do all the time. Assume something is true, then ... That's why induction doesn't work without the anchor. There are induction proofs where $P(k-1) \Longrightarrow P(k)$ but both are false. Under the assumption of $P(1)$ and $P(k-1)$ we show $P(k)$. To all who doubt $P(k-1)$ we can show that it follows from $P(k-2)$. And to all who doubt $P(k-2)$ we can show that ... and so on. In the end we land at $P(1)$ which we have shown to be true by other means. You cannot name a $k$ which we can't prove to be true by connecting all steps from $1$ on. And if there is no $k$ for which $P(k)$ is false, then it has to be true.

 

[parshyaa]

So basically you are trying to convey is that we take a random number K from a huge set of Numbers(here: N) which follows the statement and then we prove it for (k+1) then we say that simillarly P(k-1) is true because P(k-2) is true and we go on and on and on until we reaches P(1), which we have already checked therefore our assumption of P(k) is true until P(1) is true.

 

[fresh_42]

So basically you are trying to convey is that we take a random number K from a huge set of Numbers(here: N) which follows the statement and then we prove it for (k+1) then we say that simillarly P(k-1) is true because P(k-2) is true and we go on and on and on until we reaches P(1), which we have already checked therefore our assumption of P(k) is true until P(1) is true.

Yes, because in principle you can concatenate the entire chain of steps to reach $P(k)$ from the anchor $P(1)$ (or some other anchor) and get a proof for this specific number $k$. And since you can do this with any number $k$, it has to be true, because you have a proving machinery: Concatenation of known steps. Maybe the proofs will get a bit long and surely boring, but you know how to write them down. Basically one proof for every number which increases in length but that's other people's problem.

 

[member 587159]

It basically boils down to this:

You prove it for the base case (for example $n =1$). And then, you prove in general that if it works for $n = k$, then it also works for $n = k+1$. Then, you can apply this on the base case (take $k = 1$). Thus, you can conclude from the base case that $n = 2$ is true. But if $n = 2$ is true, then it is also true for $n = 3$, and so on.

This is actually the intuition behind induction, but it needs a proof

Formally, let's prove that induction works:

Theorem:

Suppose the following conditions are met:

1) $P(0)$ is true
2) $\forall k \in \mathbb{N}: P(k)$ is true implies $P(k+1)$ is true.

Then $P(n)$ is true for all $n \in \mathbb{N}$

Proof:

Let $S := \{k \in \mathbb{N}| P(k)$ is not true$\}$ and suppose (for the sake of reaching a contradiction) that $S$ is not empty. Then, by the principle of well ordering, $S$ must have a smallest element. Let's call this element $m$. Clearly, $m$ cannot be zero, since $P(0)$ is true. So $m>0$. Therefore, we can look at $m-1$, which is not an element of $S$ (because m is the minimum) so $P(m-1)$ is true.. But because of condition $2$, we find that $m$ is not in $S$. Clearly a contradiction. We conclude that S is empty and this ends the proof.

 

[Derek Hart]

In mathematical induction we prove statements using a proper technique just like in a following example:
$P(n)=n(n+1)$ is an even number for every $n∈N$

1. we will check wether $P(1)$ is True/false, its true because $P(1)=2$
2. Now We will assume that $P(k)$ is true and using this we will prove that $P(k+1)$ is also true

This is the part I don't get: Assume $P(k)$ is True

We are just assuming something is true and then 'proving' that something else is true based on that assumption. But we never proved the assumption itself is true so it doesn't seem to hold up to me. Oviously proof by induction works so am I viewing the process incorrectly?

Think of it as the domino effect. You prove that the initial domino falls, and then if any domino falls, you show that the next one must fall as well, thus showing that every domino falls ultimately due to the "motion" of the first one.

If that doesn't explain it clearly enough, think of the random "k" case to be the first domino. Then you have already shown that 2 falls, and thus that 3 falls, and etc... for all natural numbers "k".

 

[pixel]

This is the part I don't get: Assume $P(k)$ is True

We are just assuming something is true and then 'proving' that something else is true based on that assumption. But we never proved the assumption itself is true so it doesn't seem to hold up to me.

Advice from a non-mathematician:

Maybe instead of thinking of it as "assume it's true for P(k)," think of it as "if it's true for P(k)." So if P(k) is an even number, you prove P(k+1) is also even.

You showed it's true for k = 1. So based on what you proved, it's therefore true for k =2. Based on what you proved, it's therefore true for k = 3, etc.