Suppose a0, a1, a2 ,... is a sequence defined recursively as follows:
a1 = 1, a2 = 2, a3 = 3 and ak = ak-1 + ak-2 + ak-3 for all integers k > 3.
Use strong induction to show that an < 2n for all integers n ≥ 1.
To prove that an < 2n for all integers n ≥ 1 using strong induction, we need to verify two base cases and then assume a hypothesis for all k ≤ n in order to prove the statement for k = n+1.
Base cases:
1. For n = 1, we have a1 = 1. Since 2^1 = 2, we can see that a1 < 2^1 is true.
2. For n = 2, we have a2 = 2. Again, since 2^2 = 4, we can see that a2 < 2^2 is also true.
Assumption:
Assume that for all k ≤ n, it holds true that ak < 2k.
Inductive step:
Now, we need to show that a(n+1) < 2^(n+1) based on the assumption.
From the recursive definition of the sequence, we have:
a(n+1) = a(n) + a(n-1) + a(n-2)
Using the assumption, we can say that:
a(n+1) < 2n + 2(n-1) + 2(n-2)
= 2n + 2n - 2 + 2n - 4
= 6n - 6
We need to show that 6n - 6 < 2^(n+1).
We will prove this inequality by induction.
Base case:
For n = 1, 6n - 6 = 0 and 2^(n+1) = 4. Hence, the base case is true.
Assumption:
Now assume that for some k, 6k - 6 < 2^(k+1).
Inductive step:
We need to show that 6(k+1) - 6 < 2^((k+1)+1).
6(k+1) - 6 = (6k - 6) + 6 < (2^(k+1)) + 6
By utilizing the assumption, we know that 6k - 6 < 2^(k+1). Therefore:
(2^(k+1)) + 6 < (2^(k+1)) + 2^(k+1) = 2^(k+2)
Since 6(k+1) - 6 < 2^(k+2), we can conclude that the inequality holds for k = (n+1).
Therefore, we have shown that if ak < 2k for all integers k ≤ n and ak = ak-1 + ak-2 + ak-3 for all integers k > 3, then an < 2n for all integers n ≥ 1.