Proof by Strong Induction

Used for proving sequences and series.

• Requires more base cases compared to PSI
• Stronger IH compared to PSI

Structure

WTS: $\forall k\ge b,(\forall b\le i<k,P(i))⟹P(k)$

Base Cases

Assuming base cases $b,\dots ,b+k-1$

1. Let $n=b$
   1. Proof of $P(n)$
2. Let $n=b+1$
   1. Proof of $P(n)$
3. …
4. Let $n=b+k-1$
   1. Proof pf $P(n)$

Induction Step

1. Let $n\ge b+k$
2. Suppose $P(j)$ holds whenever $b\le j<n$ Induction Hypothesis
   1. Proof of $P(n)$
3. Therefore by induction, $P(n)$ holds for all $n>b$ $\square$