# Strong Induction: Example Using All of P(1) and … and P(k - 1) and P(k) to Prove P(k + 1)

I'm trying to understand how to do "real" strong induction, but my textbook seems to be of no help. It defines strong induction as follows:

Let $P(n)$ be a property that is defined for integers $n$, and let $a$ and $b$ be fixed integers with $a\leq b$. Suppose the following two statements are true:

1. $P(a), P(a+1),...,$ and $P(b)$ are all true.
2. For any integer $k\geq b$, if $P(i)$ is true for all integers $i$ from $a$ through $k$, then $P(k+1)$ is true.

Then the statement 'for all integers $n\geq a, P(n)$' is true. (The supposition that $P(i)$ is true for all integers $i$ from $a$ through $k$ is called the inductive hypothesis.

... but then shows a bunch of examples where it doesn't appear to even use it as defined... or uses it for the sake of using it where it's not needed at all.

For example, it shows the example of a recursively defined sequence...

$$a_1=1$$ $$a_2=3$$ $$a_k=a_{k-2}+2\cdot a_{k-1},\forall k\in \mathbb{N}\geq 3$$

It then asks me to show that $a_n$ is odd for all $n\geq 1$. In the solution, it shows base cases for $P(1)=a_1$ and $P(2)=a_2$, and then assumes $P(i)$. But in the proof step, it doesn't use $P(i)$ at all - it asks to consider $P(k+1)$ and uses two assumptions $P(k)$ and $P(k-1)$ to prove it. All of the examples are like this. Why use the proper definition of strong induction if you can just use normal induction with multiple base cases and multiple assumptions?

-
If you have to use more than one previous case (such as $P(k)$ and $P(k-1)$ to prove $P(k+1)$), then you're using strong induction. Are you asking for an explicit example of a problem that requires every previous case to solve inductively? – Austin Mohr Dec 3 '12 at 3:31
Considering $P(k+1)$ means you're working towards showing it is true. Then you use $P$ for $k$ and $k-1$ both of which are inductively assumed in the strong case. The point is, you need both $k$ and $k-1$ to argue that point. In weak induction you only have $k$ to work with. – James S. Cook Dec 3 '12 at 3:32
If you say suppose $P(i)$ for all $i \leq k$ then that includes $k$ and $k-1$. – James S. Cook Dec 3 '12 at 3:34
In weak induction, you prove $P(k+1)$ is true using only the fact that $P(k)$ is true. In strong induction, you prove $P(k+1)$ is true, but you're allowed to make use of any "previous" $P$ (that is, any $P(i)$ for $i \leq k$). – Austin Mohr Dec 3 '12 at 3:37
@agent154: Any use of strong induction can be replaced by ordinary induction, using essentially the trick you mention third comment above this one. In your case, let $Q(n)$ be the assertion $P(n)$ and $P(n-1)$. In general, let $Q(n)$ be the assertion $P$ holds from $a$ up to $n$. – André Nicolas Dec 3 '12 at 3:54

Consider the sequence defined recursively by

$$a_0 = 1$$ $$a_n = a_{n-1} + a_{n-2} + ... + a_0 + 1.$$

Then I claim that $a_n = 2^n$ by strong induction. Suppose the claim holds for $n = 0, 1, 2, ... k$. Then

$$a_{k+1} = a_k + a_{k-1} + ... + a_0 + 1 = 2^k + 2^{k-1} + ... + 1 + 1 = (2^{k+1} - 1) + 1 = 2^{k+1}$$

(Recall the sum formula $\frac{1-r^{n+1}}{1-r}$ for a geometric series )

and the conclusion follows. Note that it is not enough to assume that the claim holds a bounded number of steps back; I need to go all the way back to the beginning of the sequence.

-
I'm afraid that's not a great example. You can prove it easily by ordinary induction. Indeed, if you know that $$a_n = a_{n-1} + \cdots + a_0 + 1 = 2^n,$$ then $$a_{n+1} = a_n + (a_{n-1} + \cdots + a_0 + 1) = 2a_n = 2^{n+1}.$$ – James Cranch Oct 14 '13 at 15:08

A classical example of this is to prove the existence (not uniqueness) of factorization over the integers.

Theorem. Every integer greater than or equal to $2$ is the product of irreducible integers. So given $n \in \mathbb{N}$, there exist $p_1, \ldots , p_k$ (not necessarily distinct) where $p_i$ is irreducible over $\mathbb{N}$ and $n = p_1 \cdot \ldots \cdot p_n$.

We know that $2$ is irreducible. Now, (here's the inductive hypothesis), suppose that for all integers $2 \leq n < N$, $n$ has a factorization into irreducibles as described above.

Now let's inspect $N$: We have two cases.

Case 1. $N$ is irreducible, and we are done.

Case 2. $N = a \cdot b$ for some $a,b < N$. (Here's where induction comes in.) Since $a,b < n$, we know that $a = p_1 \cdot \ldots \cdot p_k$ and $b = q_1 \cdot \ldots \cdot q_l$ where each $p_i,q_j$ is irreducible, and thus $$N = p_1 \cdot \ldots \cdot p_k \cdot q_1 \cdot \ldots \cdot q_l$$ and $N$ is expressible as the product of irreducibles. $\Box$

Strong induction is very similar to normal (weak?) induction only you get more to work with. I wouldn't fret about the details, you just get to assume that your theorem holds for every integer in some range.

-
I've seen this in the book... but what confuses me still is that - by my only fresh learning of normal induction - that I don't see the inductive hypothesis of $P(i)$ readily being used as in all the normal one-base case $P(1)$ and one-hypothesis $P(k)$. Speaking with a math major a few classes ahead of me calls this kind of stuff "strong-ish" induction because it's not truly "strong"... but could he be wrong? – agent154 Dec 3 '12 at 5:00