# Define an by a0 = 1, a1 = 2, a2 = 4 and an+2 = an+1 + an + an−1, for n ≥ 1. Show that an ≤ 2n for all n ∈ N.

## Solution for Define an by a_{0} = 1, a_{1} = 2, a_{2} = 4 and a_{n+2} = a_{n+1} + a_{n} + a_{n-1}, for n ≥ 1. Show that a_{n} ≤ 2^{n} for all n ∈ N.

We use induction on n. The inequality is true for n = 0, 1 and 2. Suppose that it is true for all n ≤ k where k ≥ 2.

Then,

a_{k+1} = a_{k} + a_{k-1} + a_{k-2} ≤ 2^{k} + 2^{k-1} + 2^{k-2}

= 7 · 2^{k-2} < 2^{k+1}