Using Induction to prove this inequality?

Question

I'm having a hard time solving the following problem:

Let ${\displaystyle (a_{n})_{n\in \mathbb {N_{0}} }}$ be the sequence defined recursively by:

$a_{0}=2$

$a_{n+1} = \frac{1+3^{n+1}}{2} + \sum_{i=0}^n a_i \qquad \forall\ n \in \mathbb{N_{0}}$

Prove (by induction):

$$a_{n} \le 3^{n} + 2^n\qquad \forall\ n \in \mathbb{N_{0}} $$

Every way I tried so far gets me nowhere and I'm starting to get confused. Solutions or any hints will be highly appreciated. Thank you in advance.

Answer 1

Hint:

Using strong induction, you have \begin{align} a_{n+1}= \frac{1+3^{n+1}}{2} + \sum_{i=0}^n a_i&\le \frac{1+3^{n+1}}{2} + \sum_{i=0}^n(3^i+ 2^i)\\ & = \frac{1+3^{n+1}}{2}+\frac{3^{n+1}-1}2 + 2^{n+1}-1. \end{align} Can you end it?