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₀ = 1, a₁ = 2, a₂ = 4 and a_n+2 = a_n+1 + a_n + a_n-1, for n ≥ 1. Show that a_n ≤ 2ⁿ 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