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.

To prove this, we will use the concept of mathematical induction.

Step 1: Base Case We need to verify the inequality for the first few terms of the sequence.

For n=1, b1 = 1 which is less than 2^1 = 2. For n=2, b2 = 2 which is less than 2^2 = 4. For n=3, b3 = 3 which is less than 2^3 = 8.

So, the inequality holds for n=1, n=2, and n=3.

Step 2: Inductive Hypothesis Assume that the statement is true for n, n+1, and n+2, i.e., bn < 2^n, bn+1 < 2^(n+1), and bn+2 < 2^(n+2).

Step 3: Inductive Step We need to prove that the statement is also true for n+3, i.e., bn+3 < 2^(n+3).

By the definition of the sequence, bn+3 = bn+2 + bn+1 + bn.

By the inductive hypothesis, we can substitute each term on the right side of the equation with its upper bound:

bn+3 < 2^(n+2) + 2^(n+1) + 2^n.

We know that 2^n is less than 2^(n+1) and 2^(n+1) is less than 2^(n+2). So, we can replace 2^n and 2^(n+1) with 2^(n+2) to get an upper bound for bn+3:

bn+3 < 2^(n+2) + 2^(n+2) + 2^(n+2) = 3 * 2^(n+2).

Since 3 < 8, we have 3 * 2^(n+2) < 8 * 2^(n+2) = 2^(n+3).

Therefore, bn+3 < 2^(n+3).

So, by mathematical induction, for all positive integer n, bn < 2^n.