1. I'm trying to learn to strong induction and I'm beginning understand the steps. However I can't seem to understand why some examples have multiple base cases. What do you look for while choosing base cases?

  2. I read it almost everywhere that strong induction and weak induction are variants and that what can be proved with one can be proved with another. I just need a favor, can someone show me how to prove $1+2+3+...+n = \dfrac{n(n+1)}{2}$ using strong induction? I need to compare the two so I can understand strong induction a little better.

Thank you very much, my syllabus includes weak and strong induction both. But my textbook has merely just mentioned the definition of strong induction and all the solved examples are solved using weak induction.

  • $\begingroup$ Prime Factorization is an example of using complete (strong) induction. For proving the sum of first $n$ numbers it is enough to assume the statement holds for $n$ and show it holds for $n+1$ as can be seen here $\endgroup$
    – Jon
    Aug 12 '18 at 13:37
  • $\begingroup$ @Jon Yes I know how to prove by weak induction. I really want to see how would someone prove that with strong induction. Because I keep hearing, "whatever can be proved by one can be proved by other induction as well" so... Yea $\endgroup$
    – William
    Aug 12 '18 at 13:43
  • $\begingroup$ That would just be by assuming $\sum_{i=1}^{k}i=\frac{k\left(k+1\right)}{2}$ for every $1\leq k\leq n$ and then showing it also holds for $n+1$. The thing is when proving it also holds for $n+1$ it's enough to use only the assumption for $n$ and the rest of the asumptions for $1\leq k\leq n+1$ can be totally ignored. $\endgroup$
    – Jon
    Aug 12 '18 at 13:58
  • $\begingroup$ Strong induction includes the assumption of weak induction $\endgroup$
    – Jon
    Aug 12 '18 at 14:09
  • $\begingroup$ Strong induction is needed to prove \forall n\in \Bbb N\;(P(n)) when you don't know of a way to prove that P(n)\implies P(n+1). It is often by contradiction : Show that if \neg P(n) then there exists some m<n such that \neg P(m) (...so there could not exist a least n such that \neg P(n)...) although m is not necessarily n-1. For example to show that if p is a prime and p\not \equiv 3 \mod 4 then p=x^+y^2 for some x,y\in \Bbb Z^+, we show that if some p were a counter-example then there would be a smaller counter-example. $\endgroup$ Aug 12 '18 at 19:36

This is the best I can do for a proof by strong induction that $\forall n\in \Bbb Z^+\;(S(n)=(n^2+n)/2),$ where $S(n)=\sum_{j=1}^n j$.... that isn't an obvious re-arrangement of a proof by weak induction.

Observe that for $m,n\in Z^+,$ if $m<n$ then $$S(n)=S(m)+\sum_{j=1}^{n-m}(m+j)=$$ $$=S(m)+\sum_{j=1}^{n-m}m+\sum_{j=1}^{n-m}j=$$ $$=S(m)+(n-m)m+S(n-m).$$

Suppose $n\geq 2$ and $\forall m<n\;(\; S(m)=(m^2+m)/2.)$ Since $n>1$ there exists $m\in \Bbb Z^+$ with $n>m$ and $n>n-m\in \Bbb Z^+.$ For any such $m$ we have $$S(n)=S(m)+(n-m)m+S(n-m)=$$ $$=(m^2+m)/2+(n-m)m+((n-m)^2+(n-m))/2=$$ $$=(n^2+n)/2.$$

And the base case $n=1$ is trivial.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.