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

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

Step 1: Base Case We start with the smallest values of n. 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 statement holds for n=1, n=2, and n=3.

Step 2: Inductive Step Assume that the statement is true for n=k, n=k+1, and n=k+2, i.e., bk < 2^k, bk+1 < 2^(k+1), and bk+2 < 2^(k+2). We need to prove that the statement is true for n=k+3, i.e., bk+3 < 2^(k+3).

We know that bk+3 = bk+2 + bk+1 + bk. By the inductive hypothesis, bk+3 < 2^(k+2) + 2^(k+1) + 2^k.

Since 2^(k+2) + 2^(k+1) + 2^k = 42^k + 22^k + 2^k = 72^k < 82^k = 2^(k+3), we have bk+3 < 2^(k+3).

Step 3: Conclusion By mathematical induction, the statement is true for all positive integer n. So, for all positive integer n, bn < 2^n.