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$.

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.