I get induction.
(i) show that the statement holds when n=1 (or some basis)
(ii) show that the statement holds for a general subsequent case, $n+1$.
By PMI the statement holds for all cases.
Dominoes, and all that. I get it. It makes sense.
But when it comes to Principle of Strong/Complete Induction i don't understand why we are assuming it holds for a range. Honestly the whole 'assume' part of any induction is what gets me. Why do I need to assume anything? Isn't it adequate to show it works without assuming it?
I have added an example of PSI below.
Use PCI to prove that every natural number greater than or equal to $11$ can be written in the form $2s +5t$, for some natural numbers $s$ and $t$.
Approach:
I would think I need to show that it works for n=11, and it works for m=12, and then show how it will work for n+2 and m+2 (since both need a slightly different formula to compute).
$n=11 = 2(3) +5(1); s=3$ and $t=1$
$n=12 = 2(1) +5(2); s=1$ and $t=2$
so obviously, for each subsequent case n, you add another s to the n-2. I find it tricky to express this succinctly but here's my attempt at a proof.
Proof (by PCI):
(i) Let n be an integer greater than or equal to $11$.
When $n=11 = 2(3) +5(1); s=3$ and $t=1.$
When $n=12 = 2(1) +5(2); s=1$ and $t=2.$
Thus the statement holds for $n=11$ and $n=12$.
(ii) Assume the statement holds for $11\leq i \leq n$. Because $n\geq 13$, $n-2 \geq 11$, so $n-2 = 2s =5t$ for some $s$, $t$ in $\mathbb{N}.$
Therefore $n=2(s+1) +5t$.
Therefore, by PCI, every natural number greater than or equal to $11$ can be written in the form $2s +5t$, for some natural numbers $s$ and $t$.
In some problems, the truth of the $(k+1)$-st case can require that more than just the $k$th case be true (maybe all cases, $1$ through $k$ are required). In these cases, strong induction, or a variant thereof is required (so that you have the relevant preceding cases true in order to complete the inductive step).
All proofs by induction are made up of two key parts: The base case, and the inductive step.
In the inductive step, you assume the truth of the $k$th case (or in the strong variant, all cases up to $k$) and use that to prove that the $(k+1)$-st case holds. What you establish in this step is the implication:
Previous case(s) $\Rightarrow$ Next case
This, of course, is a conditional statement, and hence, does not, on it's own, suffice to prove the original proposition (that it's true for all cases). This is what the base case does. It 'starts the dominoes falling'.
With the base case proven, then you get a chain of implications:
Base case $\Rightarrow$ 2nd case
With base case true, therefore 2nd case is true
2nd case (and base case in strong version) $\Rightarrow$ 3rd case
etc.
thus all cases in the chain are true (this is the dominoes falling part of the induction).