Strong vs weak induction

Question

My professor in a proof class said very explicitly several times that "strong induction is a more powerful proof technique then weak induction and is preferred over weak induction".

Anywhere I have looked online and in textbooks it says that weak induction and strong induction are equivalent. Just sometimes one is preferred to use over the other depending on the situation.
Can you prove anything with strong induction that you can prove with weak induction and vice versa? Are they interchangeable?

If someone could comment on both points that would be great!

With the answer below given to you (to which I also agree), you might want to ask the professor WHY he prefers the "strong" version, without stepping on his toes? — imranfat, Jan 26 '20 at 19:46
Does this answer your question? Examples where Strong Induction is more useful than "Regular" Induction? — , Apr 13 '20 at 08:27

score 1 · Accepted Answer · answered Jan 26 '20 at 19:43

1

They are entirely interchangeable, and the only reason to pick one over the other is aesthetics.

The basic gist of it is, if you only need the previous step, assume only the previous step. If you need all previous steps, assume all previous steps. (And if you need the two previous steps, assume the two previous steps, and so on.) A proof usually looks better that way.

answered Jan 26 '20 at 19:43

Arthur

199,419

So any proof you can do with strong induction you can also do with weak induction? – Mark Jan 26 '20 at 19:57
@Mark Yes, and the other way around. – Arthur Jan 26 '20 at 20:15

Strong vs weak induction

1 Answers1