Question about mathematical induction

In summary: The random number you pick is not random, because you can pick any natural number. But the important part is that you can pick any natural number and you can always prove it. That's the trick.
  • #1
parshyaa
307
19
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?
 
Last edited:
Mathematics news on Phys.org
  • #2
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.
 
  • Like
Likes mfb
  • #3
parshyaa said:
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.
 
Last edited:
  • Like
Likes Logical Dog and parshyaa
  • #4
SlowThinker said:
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
 
  • #5
parshyaa said:
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.
 
  • #6
parshyaa said:
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.
 
  • Like
Likes parshyaa
  • #7
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.
 
  • #8
parshyaa said:
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.
 
  • Like
Likes parshyaa
  • #9
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.
 
  • Like
Likes parshyaa
  • #10
parshyaa said:
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".
 
Last edited:
  • #11
parshyaa said:
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.
 
  • Like
Likes parshyaa

Related to Question about mathematical induction

1. What is mathematical induction?

Mathematical induction is a proof technique used to prove that a statement holds for all natural numbers. It involves showing that the statement is true for a base case, typically n=1, and then proving that if the statement holds for some arbitrary value of n, it must also hold for n+1.

2. Why is mathematical induction useful?

Mathematical induction is useful because it allows us to prove statements about an infinite set of numbers, such as all natural numbers, without having to individually check each case. It also provides a rigorous and logical way to prove mathematical statements.

3. What is the difference between strong and weak induction?

In strong induction, the base case is n=1 and the inductive step assumes that the statement holds for all values up to n. In weak induction, the inductive step only assumes that the statement holds for n, and the base case is typically n=0. Strong induction is more powerful and can be used to prove more statements, but both methods are equally valid.

4. Can mathematical induction be used to prove any statement?

No, mathematical induction can only be used to prove statements about natural numbers. It cannot be used to prove statements about real numbers, for example, as there is no concept of a "next" number in the set of real numbers.

5. Are there any common mistakes to avoid when using mathematical induction?

Yes, some common mistakes when using mathematical induction include assuming that the statement holds for all values up to n without actually proving it, incorrectly manipulating inequalities in the inductive step, and using the wrong base case. It is important to carefully and logically follow each step of the proof in order to avoid these mistakes.

Similar threads

Replies
13
Views
1K
Replies
5
Views
2K
Replies
7
Views
3K
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
Replies
2
Views
1K
  • General Math
Replies
5
Views
3K
  • General Math
Replies
26
Views
4K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
Back
Top