When to use weak, strong, or structural induction?

Question

For weak induction, we are wanting to show that a discrete parameter n holds for some property P such that P(n) implies P(n+1).

For strong induction, we are wanting to show that a discrete parameter n holds for some property P such that (P(1) ^ P(2) ^ ... ^ P(n))implies P(n+1), i.e. stronger assumption set.

For structural induction, we are wanting to show that for a discrete parameter n holds such that: (∀n, n∈S)P(n)

Strong induction and weak inductions are instances of the more general structural induction form. The different inductive forms are equivalent in power any any proof written in one inductive form can be written in the other inductive forms.

Certain properties or recurrences need to be approached in certain ways using the listed inductive techniques. Some properties are much harder to prove with weak induction, but are more straight forward with strong induction or structural induction; however, with strong induction even if the recurrence isn't quite visible one could use the "Master Theorem", (Intro to Algo, Cormen [et al.]- 3rd edition), to solve for the recurrence, and then approach it with weak induction or structural induction.

Are certain types of properties, recurrences, or recursive definitions best suited for certain inductive techniques and does a problem space indicate which technique should be used?

Answer 1

This was from a slide I studied earlier this semester. Maybe it will help:

Normal(weak) induction is good for when you are shrinking the problem size by exactly one.

• Peeling one Final Term off a sum
• Making one weighing on a scale
• Considering one more action on a string

Strong induction is good when you are shrinking the problem, but you can't be sure by how much.

• Splitting a set into two smaller sets
• Taking the remainder of one number divided by another

Weak Induction is a consequence of the Well Order Principle and a special case of Structural Induction as you mentioned before. Structural induction is appropriately used to build sets from recursive definitions, or given a recursive function a solution may have a unique closed form solution that can be shown using structural induction: see Binet's Formula for the nth Fibonacci Number.

But as a general thoughts: induction is used to show that all elements of an infinite set have a specified property, your inductive hypothesis may have more to do with your inductive technique rather than the problem space in general (although they do seem every related), and mathematical induction is is an instance of structural induction, not just over natural numbers, but of inductively-defined types. (For instance you can think of the natural numbers as an inductively-defined type and give a structural induction to show this is the case.) Most everything else will come after working 100 different problems of different types, being able produce these proofs quickly, and then given a problem you will make your own inductive reasoning about its property, or rather its property and your experience having worked so many problems will lend a hand in the inductive approach you will use. (I hope at least one sentence helped. I've been there.)