$a_n=\lfloor(3+\sqrt5)^n\rfloor+1$
Proof for every n that $a_n$ is divided by $2^n$ without a reminder.
I know I need to use a recursive formula since it's the subject of my assignment and I tried to finding one that it's solution is $b_n=(3+\sqrt5)^n + (3-\sqrt5)^n$ so it will help with the proof but with no success.
Edit: I solved the question thanks to Peter's help but I would still appreciate an answer to compare the induction. Thank you in advance.
If you have a linear homogenous recurrence of the form $c_n = \alpha c_{n-1} + \beta c_{n-2}$ then the standard technique to find solutions is to assume that you have a solution of the form $c_n = kx^n$, whence $kx^n = \alpha kx^{n-1} + \beta kx^{n-2}$, or $x^2 = \alpha x + \beta$. Then you find candidates for $x$ by solving the characteristic polynomial $x^2-\alpha x - \beta = 0$ and form the general solution to the recurrence by adding a weighted specific solution per root: i.e. $c_n = k_1 x_1{}^n + k_2 x_2{}^n$.
Here you have the second form, so you can apply the technique in reverse. In other words, your characteristic polynomial is $(x-3-\sqrt 5)(x-3+\sqrt 5)=0$. Multiply out to get $x^2 - 6x + 4 = 0$, so your recurrence is $b_n = 6b_{n-1} - 4b_{n-2}$.
Rewriting that as $b_n = 2(3b_{n-1}) - 2^2(b_{n-2})$ justifies the inductive step of a proof by induction that $2^n \mid b_n$, so that just leaves the identification of $a_n = b_n$ and the base cases of the induction: $b_0 = 2$ and $b_1 = 6$.