Suppose a0, a1, a2 ,... is a sequence defined recursively as follows:

Question

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.