Prove that $\left(\frac{3+\sqrt{17}}{2}\right)^n + \left(\frac{3-\sqrt{17}}{2}\right)^n$ is always odd for any natural $n$. 
Prove that $$\left(\frac{3+\sqrt{17}}{2}\right)^n + \left(\frac{3-\sqrt{17}}{2}\right)^n$$
is always odd for any natural $n$.

I attempted to write the binomial expansion and sum it so the root numbers cancel out, and wanted to factorise it but didn't know how. I also attempted to use induction but was not sure how to proceed.
 A: HINT:
Say $\left(\frac{3+\sqrt{17}}{2}\right)=a$ and $\left(\frac{3-\sqrt{17}}{2}\right)=b$.
Now observe that:
$$\left(\frac{3+\sqrt{17}}{2}\right)^n + \left(\frac{3-\sqrt{17}}{2}\right)^n$$
$$=a^n+b^n$$
$$=(a+b)(a^{n-1}+b^{n-1})-ab(a^{n-2}+b^{n-2})$$
$$=\color{red}{3\cdot\left[\left(\frac{3+\sqrt{17}}{2}\right)^{n-1}+ \left(\frac{3-\sqrt{17}}{2}\right)^{n-1}\right]+ 2\cdot \left[\left(\frac{3+\sqrt{17}}{2}\right)^{n-2} + \left(\frac{3-\sqrt{17}}{2}\right)^{n-2}\right]}$$
Now use strong induction and see what you can do.
P.S. $3 \times \mathrm{odd} + 2\times \mathrm{odd} = \mathrm{odd + even} = \mathrm{odd}$
Hope this helps you.
A: A high-powered solution comes from looking at the expression $ 2 $-adically. Indeed, by choosing an embedding $ \mathbf Q(\sqrt{17}) \to \mathbf Q_2 $ and noting that we have a sum of the form $ \alpha^n + \beta^n $, we note that $ \alpha + \beta = 3 $ is odd. It follows that one of $ \alpha, \beta $ is odd and the other one is even in $ \mathbf Z_2 $, and thus, upon reduction modulo $ 2 $, the same is true for $ \alpha^n, \beta^n $ for any $ n \geq 1 $; and thus $ \alpha^n + \beta^n $ is odd.
A: Note that it satisfies the following recursive formula:
$$a_{n+2}=3a_{n+1}+2a_n\tag{$\star$}$$
where $a_n=\left(\frac{3+\sqrt{17}}2\right)^n+\left(\frac{3-\sqrt{17}}2\right)^n$.
Thus, if $a_{n+1}$ is odd, then $a_{n+2}$ is odd.

$(\star)$ comes from noting that
$$a^2=3a+2\implies a=\frac{3\pm\sqrt{17}}2$$
And applying theories of linear recursives.
This technique is famous, take the Fibonacci sequence for example:
$$a_{n+2}=a_{n+1}+a_n\implies a^2=a+1$$
This quadratic has two solutions $a=\phi,-\phi^{-1}$.  Thus, the Fibonacci sequence has the following formula:
$$a_n=\frac{\phi^n-(-\phi)^{-n}}{\sqrt5}$$
where $\phi$ is the golden ratio.
