Consider the sequence defined by b1 = 1, b2 = 2, b3 = 3, bn+3 = bn+2 + bn+1 + bn. Show that for all positive integer n, bn < 2^n

Step 1: Understanding the Problem We need to prove that for all positive integers n, the sequence bn defined by b1 = 1, b2 = 2, b3 = 3, bn+3 = bn+2 + bn+1 + bn, satisfies bn < 2^n.

Step 2: Base Case For n = 1, 2, 3, we have b1 = 1 < 2^1, b2 = 2 < 2^2, and b3 = 3 < 2^3. So, the statement holds for n = 1, 2, 3.

Step 3: Inductive Step Assume that for some positive integer k, bk, bk+1, bk+2 all satisfy the inequality bk < 2^k, bk+1 < 2^(k+1), bk+2 < 2^(k+2). We need to show that bk+3 = bk+2 + bk+1 + bk also satisfies the inequality bk+3 < 2^(k+3).

Step 4: Proof By the inductive hypothesis, we have bk+3 = bk+2 + bk+1 + bk < 2^(k+2) + 2^(k+1) + 2^k.

Since 2^(k+2) + 2^(k+1) + 2^k < 2^(k+2) + 2^(k+2) + 2^(k+2) = 3 * 2^(k+2), and 3 * 2^(k+2) = 2^(k+3) when k ≥ 1, we have bk+3 < 2^(k+3).

Step 5: Conclusion Therefore, by mathematical induction, we have shown that for all positive integers n, bn < 2^n.