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

• Hint $\$ They satisfy a recursion $\, a_{n+1}= 3a_n + 2a_{n-1}$ arising from Newton's identities for expressing power sums in terms of elementary symmetric polynomials, viz. $$\rm\quad\ \: x^{n+1}+y^{n+1}\ =\ (\color{#c00}{x+y})\ (x^n+y^n) -\ \color{#c00}{xy}\: (x^{n-1}+y^{n-1})\quad for\ \ all\ \ \ n \ge 1\qquad\quad$$ where in the OP we have $\,\color{#c00}{x+y} = 3,\ \color{#c00}{xy} = -2.\ \$ – Bill Dubuque Feb 22 '17 at 14:45
• Dumb question: how do we know it is an integer for any natural n? – BCLC Feb 22 '17 at 14:53
• @BCLC : it is an algebraic integer (since $17 \equiv 1 \pmod 4$), and it is rational since it is fixed by the Galois group of $\Bbb Q(\sqrt{17})$. See here. – Watson Feb 22 '17 at 14:59
• – lab bhattacharjee Feb 22 '17 at 16:12

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.

• You need $a_{n+1}$ to be odd... – lhf Feb 22 '17 at 14:33
• very simple, but slightly non-obvious +1 – Paramanand Singh Feb 22 '17 at 14:34
• @ParamanandSingh The way one might reverse engineer the recurrence relation is this: The general solution to the recurrence relation $a_{n + 2} = B a_{n + 1} + C a_n$ for $B, C$ constant is (except in the special case that $B^2 = -4C$) $a_n = P r_+^n + Q r_-^n$, where $r_{\pm}$ are the roots of the characteristic polynomial $r^2 - B r - C$ and $P, Q$ are constant. On the other hand, we can write this as $(r - r_+)(r - r_-)$, so that $B = r_+ + r_-$ and $C = -r_+ r_-$. Substituting the given values for $r_{\pm}$ yields $B = 3$ and $C = 2$. – Travis Feb 22 '17 at 14:44
• @ParamanandSingh Yes, it's certainly nonobvious, which together with its efficiency makes the answer clever. One way one might be reminded of such a method here is to note the similarity of the given expression here with the explicit form $F_n = \frac{1}{\sqrt{5}} \phi^n - \frac{1}{\sqrt{5}} \bar{\phi}^n$ (sometimes called Binet's Formula) for the $n$th Fibonacci number (here $\phi$ is the Golden Ratio and $\bar\phi$ is its algebraic conjugate), and (as again I'm sure you know) $(F_n)$ is probably the best-known sequence usually defined via recursion. – Travis Feb 22 '17 at 14:57
• @Travis: Fibonacci is too famous! And yes I should have been reminded of the similarity of this sequence in question with Binet formula for Fibonacci. Then it would have been obvious that we need recurrence here. But somehow "Simply Beautiful Art" types the answer fast enough to leave no room for all these thoughts. – Paramanand Singh Feb 22 '17 at 15:02

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.

• Easier to just reproduce quadratics with the right roots, but this is good nonetheless. – Simply Beautiful Art Feb 22 '17 at 14:41
• Thanks! Would've been obvious I think, if our school curriculum contained the $a^n+b^n$ identity, which I'm not familiar with. I'll get back to this question after later tomorrow, when I seek out for the intended solution from the textbook from which this was taken. Nevertheless, I still like this answer! – Vepir Feb 22 '17 at 15:16
• @DushDushDush you could consider factoring by setting equal to zero and solving for roots. – Simply Beautiful Art Feb 22 '17 at 15:18
• @SimplyBeautifulArt The intended solution is similar to this answer but it dose not use $a^n+b^n$ identity directly, making itself unnecessary more complex. – Vepir Feb 23 '17 at 12:53
• @DushDushDush ah, interesting. I suppose they didn't want to throw that at you. – Simply Beautiful Art Feb 23 '17 at 12:54

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.