0

[1]: https://i.stack.imgur.com/kFzR9.png

In this example, I don't see what differs strong induction from ordinary induction. If I was doing this problem with ordinary induction, I would prove the base case and then for $P\left(n+1\right)$ just like this example. Why this is considered as strong induction?

Book: Discrete mathematics and it's applications by Susanna S. epp.

Nerrit
  • 402
Ali
  • 45
  • 3
    Regular induction simply assumes $P(n)$ to prove $P(n+1)$. It doesn't necessarily assume $P(n-1), P(n-2),...$ etc. Strong induction also assumes these as well. Many people typically intuitively use strong induction even while doing regular induction and frankly the distinction doesn't matter much practically speaking. – Vercingetorix Jan 01 '23 at 15:20
  • @Vercingetorix I know that but i don't see where the difference in this example. It looks like ordinary induction, is this a bad example for using strong induction? – Ali Jan 01 '23 at 15:22
  • 5
    In the non-prime case they are using $P(a)$ and $P(b)$ – Vercingetorix Jan 01 '23 at 15:23
  • 1
    ... and in general $a < k$ and $b < k,$ so merely knowing that $P(k)$ is true would be no use in proving that $P(k+1)$ is true. But @Vercingetorix why is that a comment and not an answer? – David K Jan 01 '23 at 16:00

0 Answers0