Sequence problem by Strong induction

Question

Problem is as follows:

Let $X_0 = 3$ and let $X_{n+1} = X_n + \cdots + x_1 + x_0 + 3$ for $n ≥ 0$. Show that $3|X_n$ for all $n ≥ 0$.

I have the base case where $n=0$. Therefore $X_0=3$ and $3|0$. Where do I go next?

Answer 1

Induction hypothesis: Assume $3|x_k, \forall k \le n$.

Induction step: $x_{n+1} = x_n + x_{n-1}+\cdots + x_1 + x_0 + 3$. Each of these $x_i$ is divisible by $3$, also $3|3$. We also know that if $3|a, 3|b \implies 3 | (a+b)$. Therefore, $3|\sum\limits_{k = 0}^n x_k + 3 = x_{n+1}$. Hence proved.