I don't see a clear difference between $(ii)$ and $(ii')$, is $(ii')$ referring to k being a specific integer along the positive integer line whereas $(ii)$ is referring to any integer of k? (sorry if i'm missing something obvious)
Asked
Active
Viewed 94 times
0
-
2The condition (ii) says that $k\in S\implies k+1\in S$, i.e., your inductive hypothesis is that $k\in S$ and the inductive step is showing that this implies $k+1\in S$. But condition (ii') says that $1,2,\ldots ,k\in S$, i.e., your inductive hypothesis is that $1,2,\ldots ,k\in S$ and the inductive step is showing that $k+1\in S$. This second form of induction is called strong induction. – Prasun Biswas Jun 09 '17 at 22:44
-
couldn't you also say that $(ii')$ says that k∈S⟹k+1∈S ? – Sonny Da Silva-Peters Jun 09 '17 at 22:48
-
sorry idk what happened only saw the first half my bad, thank you – Sonny Da Silva-Peters Jun 09 '17 at 22:48
-
1Well, the second theorem is just an extension of the first. In the standard version, you just assume that the proposition $P(x)$ is true for $k$, i.e., $P(k)$ is true and show that this implies $P(k+1)$ is true. When just assuming that $P(k)$ is true doesn't help us in showing that $P(k+1)$ is true, we can use the stronger form where we assume that $P(1),P(2),\ldots ,P(k)$ are all true and try to show that by assumings all of them to be true, we can imply that $P(k+1)$ is true. – Prasun Biswas Jun 09 '17 at 22:55
-
I understand it now, thank you for your help – Sonny Da Silva-Peters Jun 09 '17 at 22:59
1 Answers
0
The condition $(ii)$ says that $k\in S⟹k+1\in S$, i.e., your inductive hypothesis is that $k\in S$ and the inductive step is showing that this implies $k+1\in S$. But condition $(ii')$ says that $1,2,…,k\in S$ i.e., your inductive hypothesis is that $1,2,…,k\in S$ and the inductive step is showing that $k+1\in S$. This second form of induction is called strong induction. – Prasun Biswas (I just thought it would be helpful to have it as an answer)