I'm currently taking a discrete math course and came over strong vs weak induction. I conceptually understand the two and understand that one can always use strong induction, however using weak induction might be easier or vice versa (depending on the question).
My question is this: Is there a general rule of thumb that makes a question easier to solve using strong induction?
Thanks in advance!
On
I agree that sometimes in an induction proof it's hard to show that a statement $S_k \implies S_{k+1}$, so that's when I resort to strong induction. After all, it may be easier to show some "lower" $S_m$, where $m < k$ implies $S_k+1$. Honestly, it's really difficult (at least for me) to know when strong or weak induction is more useful; you'd just have to get your hands dirty. (It's like how if you see a complicated integral, it's not clear what substitution to use, if you should use Cauchy's Residue Theorem, if you should integrate by parts, etc.)
Let's use an example of how a proposition that looks like it can be proved using induction actually turns out to be harder than we expected.
$$\text{Prove that } 12 \mid \left(n^4-n^2\right) \text{ where } n \in \mathbb{N}.$$
Let's use regular (weak) induction. The base case is that if $n=1$ then we get $12$ divides $0$, which is true. Next for our inductive step, let's fix $n = k$ and assume that $12 \mid \left(k^4-k^2\right)$. That can be written as $k^4 - k^2 = 12b$ where $b \in \mathbb{Z}$. We also have that, after doing some algebra,
$$(k+1)^4 - (k+1)^2 = 12b + 4k^3 + 6k^2 + 2k.$$
Now we're stuck because we can't factor out a $12$, but fortunately, strong induction is another tool to prove the proposition.
To be perfectly clear: “weak” induction is strong induction implicitly, if you will. The use case for strong and weak induction depend on what you are trying to prove.
For example, to prove $$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6},$$ you don't “need” to use strong induction, because if you show that it works for the base case $n = 1$, then assuming that it holds for some positive integer $m \ge 1$ is enough to then show that it will also hold for $m + 1$.
However, there are cases where you need not only to assume that it holds for the base case and some integer $m \ge 1$, but also that it holds for $1,2,\dots,m$. Of course, once again, you still do this implicitly when you use weak induction.
An example for where you did have to explicitly use it is perhaps recursion.
For example, say $x^{-1} + x$ is an integer for some $x \in \mathbb{R} \setminus \{0\}$, then we wish to prove that $$\frac{1}{x^n} + x^n$$ is also an integer. We can define a recursion: $a_i = \frac{1}{x^i} + x^i$. Then $a_1$ is our base case, and we assume that $a_i$ holds for $1 \le i \le m$, for some positive integer $m$. Now observe that: $$\frac{1}{x^{m+1}} + x^{m+1} = \underbrace{ \left( \frac{1}{x^{m}} + x^{m} \right) }_{\text{integer by inductive } \\ \text{hypothesis on } m} \underbrace{\left( \frac{1}{x} + x \right)}_{\text{base case integer}} - \underbrace{\left( \frac{1}{x^{m-1}} + x^{m-1} \right)}_{\text{integer by inductive} \\ \text{hypothesis on } m-1}.$$
If we were to write this as a recursion: $a_{m+1} = a_m a_1 - a_{m-1}$. Using weak induction, we wouldn't be able to complete the proof this way because we wouldn't know that $x^{-(m-1)} + x^{m-1}$ (or $a_{m-1}$) is an integer.
To summarize: