1
$\begingroup$

I have a question regarding strong and weak induction.

During my studies only weak induction has been formally introduced but at some point I started using strong induction whenever I had something to prove for positive integers. I have some concerns about how to show to my students the difference between two of them and when is one better than another. See this example

(Exercise 19 from this book) Show that each integer $n>7$ can be written as a sum containing only the numbers $3$'s and $5$'s. For example: $8=3+5$, $9=3+3+3$, $10=5+5$.

My proof (strong induction): Base cases are already shown in the statement. Suppose that the statement is true for all numbers $11\leq n\leq k$. Now, let us observe number $n=k+1$. We have $$k+1=(k-2)+3,$$ and $k-2$ can be written with only $3$'s and $5$'s by the inductive assumption (and the base case) since $k-2\geq 9$. So we have proven our statement.

Solution from the book (weak induction):
enter image description here

My concern is if my use of strong induction is wrong in this case in some way, or just not "pretty enough" for this problem?

Is there any reason why it is not good idea to tell students of introductory class in number theory that they can use strong induction whenever they feel they need it? Is it wrong to write assumption as in the strong case every time, even if you use only $k$ to prove $k+1$?

|cite|improve this question
$\endgroup$
  • $\begingroup$ It's fine either way. Your version is simpler (quicker and easier to see at a glance), but in defense of the book, since strong induction can be easily avoided, the author chose to stay with the more elementary version (i.e., ordinary induction). $\endgroup$ – quasi Mar 1 '18 at 9:10
  • $\begingroup$ @quasi I also like the proof from the book better :) Even though the strong induction always cross my mind first! But in this case proof with strong induction is almost trivial $\endgroup$ – Meow Mar 1 '18 at 9:12
  • $\begingroup$ @quasi Since strong induction always works, whereas ordinary induction only works for the natural numbers, one might also ask: Why ever bother with ordinary induction? $\endgroup$ – Tobias Kildetoft Mar 1 '18 at 9:13
  • 1
    $\begingroup$ @Tobias Kildetoft: Well, ordinary induction is conceptually simpler, so for a problem where strong induction isn't needed, and offers no saving of steps, why use it? $\endgroup$ – quasi Mar 1 '18 at 9:17
1
$\begingroup$

Induction works on a set $A$ that is equipped with a relation $R\subseteq A\times A$ such that every non-empty subset $B$ of $A$ contains an element $b\in B$ with $\{x\in A\mid x \mathrel{R} b\}\cap B=\varnothing$.

If you are interested then this answer gives you some further information.

A relation that satisfies this is by definition "well-founded".

On set $\mathbb N$ the relation $<$ is well-founded and the induction connected with $<$ is what we call "strong induction".

But if a relation $R$ is well-founded then so is any $S\subseteq R$.

Turning back to $\langle\mathbb N,<\rangle$ we have $S:=\{\langle n,m\rangle\mid m=n+1\}\subseteq\{\langle n,m\rangle\mid n<m\}$ and applying $S$ in stead of $<$ is what we call "ordinary induction".

IMHO working with $<$ is more natural and evidently has profits (since the induction hypothese is a stronger one). I really cannot find any disadvantages and would even plead for teaching strong induction before teaching ordinary induction.

|cite|improve this answer
$\endgroup$

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.