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:
- $P(a), P(a+1),…,$ and $P(b)$ are all true.
- 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?
Best Answer
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.