Question

Let a0 = 1, a1 = 2, a2 = 3 and an = an-1 + an-2 + an-3 for n ≥ 3. Prove that an ≤ 3n for all positive integers n.

​

Answer 1

Given:

Let a0 = 1, a1 = 2, a2 = 3 and an = an-1 + an-2 + an-3 for n ≥ 3.

To Prove:

Prove that an ≤ 3n for all positive integers n.

Solution:

it is given that a0 = 1, a1 = 2, a2 = 3

and we know that d =  common difference is-

$d=a_{1} -a_{0} =a_{2}-a_{1}$

here,

$d=1 =2-1=a_{1} -a_{0} \\d=1=3-2=a_{2} -a_{1}$

also , we know that-

$a_{n} = a_{0}+(n-1)(d)$

therefore, in $a_{n}= a_{n-1} + a_{n-2} + a_{n-3}$  R.H.S. is

$=a_{n-1} +a_{n-2} +a_{n-3} \\=(a_{0}+((n-1)-1)d)+(a_{0}+((n-2)-1)d)+(a_{0}+((n-3)-1)d) \\=(a_{0}+(n-2)d)+(a_{0}+(n-3)d)+(a_{0}+(n-4)d)\\=(1+(n-2)1)+(1+(n-3)1)+(1+(n-4)1)\\=1+n-2+1+n-3+1+n-4\\=3n-6\\\leq 3n$

for $n\geq 3$,

from above, calculation

$a_{n} \leq 3n$ for all positive integers n.