# The number $(3+\sqrt{5})^n+(3-\sqrt{5})^n$ is an integer

Prove by induction that this number is an integer:

$$u_n=(3+\sqrt{5})^n+(3-\sqrt{5})^n$$

### Progress

I assumed that it holds for $$n$$ and I tried to do it for $$n+1$$ but the algebra gets quite messy and I'm unable to prove that the following term is an integer: $$\sqrt{5}((3+\sqrt{5})^n-(3-\sqrt{5})^n)$$

• What did you try ? – Claude Leibovici Aug 23 '14 at 4:29
• I assumed that it holds for $n$ and I tried to do it for $n+1$ but the algebra get quite messy and I'm unable to prove that the following term is an integer :$\sqrt{5}((3+\sqrt{5})^n-(3-\sqrt{5})^n)$ – Keith Aug 23 '14 at 4:33
• @user143201 It's much less messy (almost trivial!) if you exploit the innate algebraic symmetry - here the multiplicativity of the conjugation map $\,\alpha = j + k\sqrt{5}\,\to\, \bar\alpha = j-k\sqrt{5}.\$ See my answer for details. – Bill Dubuque Aug 23 '14 at 17:34
• – Watson Dec 24 '16 at 12:44

Outline: For the (strong) induction step, we can use the fact that $$(3+\sqrt{5})^{n+1}+(3-\sqrt{5})^{n+1}=\left[(3+\sqrt{5})^{n}+(3-\sqrt{5})^{n}\right]\left[(3+\sqrt{5})+(3-\sqrt{5})\right]-(3+\sqrt{5})(3-\sqrt{5})\left[(3+\sqrt{5})^{n-1}+(3-\sqrt{5})^{n-1}\right].$$

Note that $(3+\sqrt{5})+(3-\sqrt{5})$ and $(3+\sqrt{5})(3-\sqrt{5})$ are integers.

Remark: There are better "non-induction" ways. For example, imagine expanding each of $(3+\sqrt{5})^n$ and $(3-\sqrt{5})^n$, using the Binomial Theorem. Now add. The terms in odd powers of $\sqrt{5}$ cancel.

• In general, if you have a monic polynomial $x^2+ax+b$ with integer coefficients and (possibly complex) roots $\alpha,\beta$, $\alpha^n+\beta^n$ is an integer for any $n$, from $\alpha+\beta=-a$, $\alpha\beta=b$ integers and $\alpha^{n+1}+\beta^{n+1}=(\alpha^n+\beta^n)(\alpha+\beta)-\alpha\beta(\alpha^{n-1}+\beta^{n-1})$. – Pedro Tamaroff Aug 23 '14 at 4:49
• @PedroTamaroff: Your comment is clearer than my answer, an example of how greater generality can be simpler. – André Nicolas Aug 23 '14 at 4:52
• Does induction holds for $n-1$ ? – Keith Aug 23 '14 at 5:04
• You can frame the argument as strong induction. (If the result holds for all $k\le n$, it holds at $n+1$). For details, please see Wikipedia or your book. Or we can frame it as ordinary induction, letting $P(n)$ be the assertion that the expression is an integer at $n-1$ and $n$. Verify that $P(1)$ holds (two things to check). Then use the formula displayed in the answer to show that if $P(n)$ holds then $P(n+1)$ holds. – André Nicolas Aug 23 '14 at 5:37
• @Pedro Another simple way to view it is via the multiplicativity of conjugation - see my answer. – Bill Dubuque Aug 23 '14 at 17:38

From the theory of sequences defined by a linear recurrence relation with constant coefficients, the sequence $u_n$ satisfies $u_{n+2}=6u_{n+1}-4u_n$ and $u_0=2$ and $u_1=6$.

Then, if you assume that $u_n$ and $u_{n+1}$ are integers, it follows immediately that $u_{n+2}$ is also an integer. You can write a strong induction from this to have a complete proof.

Hint $$\,$$ By induction $$\,\alpha^n,\,\overline\alpha^{\,n} = j \pm k\sqrt{5}\,$$ are $$\,\color{#c00}{\rm conjugate}\,$$ (so their sum $$= 2j\in\Bbb Z)$$

with easy inductive step: $$\,\ \overline{\alpha^{n+1}} =\, \color{#0a0}{\overline{\alpha\,\alpha^n} =\,\overline\alpha}\,\color{#c00}{\overline{\alpha^n}}\,\overset{\color{#c00}{\rm induct}}=\overline\alpha\,\color{#c00}{{\overline\alpha}^n} = {\overline\alpha}^{\,n+1}\$$ by $$\ \color{#0a0}{\overline{xy}\, =\, \overline x\, \overline y}$$

Remark $$\$$ Hence we see that the proof is a special case of the $$n$$-ary inductive extension of the $$\color{#0a0}{\text{multiplicativity}}$$ of conjugation, i.e $$\ \overline{\alpha_1\cdots \alpha_n}\, =\, \overline\alpha_1\cdots \overline\alpha_n,\,$$ in our special power case $$\,\alpha_i = \alpha$$. The same proof works for any quadratic integer $$\,\alpha.\,$$ As always: exloit innate symmetry!

See this answer for an extension to computing the parity of such power sums.

Let $v_n = (3+\sqrt{5})^n - (3-\sqrt{5})^n$, then $$u_1 = 6, v_1 = 2\sqrt{5}$$ And $$u_{n+1} = (3+\sqrt{5})(3+\sqrt{5})^n + (3-\sqrt{5})(3-\sqrt{5})^n = 6u_n + \sqrt{5}v_n$$ $$v_{n+1} = (3+\sqrt{5})(3+\sqrt{5})^n - (3-\sqrt{5})(3-\sqrt{5})^n = 6v_n +\sqrt{5}u_n$$ If $v_n$ is an integer multiple of $\sqrt{5}$ and $u_n$ is an integer, then $v_{n+1}$ is an integer multiple of $\sqrt{5}$ and $u_{n+1}$ is an integer.

If $n$ is odd then for all reals $x, y$ we have $$(x+y)^{n} + (x-y)^{n} = 2x^n + 2\sum_{j\ \text{odd}}\binom{n}{j}x^{j}y^{n-j};$$ if $n$ is even then for all reals $x, y$ we have $$(x+y)^{n} + (x-y)^{n} = 2x^n + 2y^n + 2\sum_{j\ \text{even}}\binom{n}{j}x^{j}y^{n-j}.$$ Putting $x := 3$ and $y := \sqrt{5}$ finishes the proof, for the irrational terms are all cancelled out.

See here -- the solutions of $a_n=Aa_{n-1}+Ba_{n-2}$ are given by $a_n=C\lambda_1^n+D\lambda_2^n$ if $\lambda_1\neq \lambda_2$, where $C,D$ are constants created by $a_0,a_1$, and $\lambda_1, \lambda_2$ are the solutions of $\lambda^2-A\lambda-B=0$ (the characteristic polynomial), and $a_n=C\lambda^n+Dn\lambda^n$ if $\lambda_1=\lambda_2=\lambda$.

$u_n=(3+\sqrt{5})^n+(3-\sqrt{5})^n$.

In this case, you want $\lambda_1=3+\sqrt{5}$, $\lambda_2=3-\sqrt{5}$, $C,D$ created by $u_0=2$, $u_1=6$.

Apply Vieta's formulas.

$\lambda_1+\lambda_2=6=A$, $\lambda_1\lambda_2=4=-B$.

The characteristic polynomial is $\lambda^2-6\lambda+4=0$.

The recurrence relation is $u_{n+1}=6u_n-4u_{n-1}$ with $u_0=2$, $u_1=6$.

$u_n$ is an integer because $u_0$, $u_1$ are integers and the recurrence relation shows that $u_2=6u_1-4u_0\in\mathbb Z$, etc. You could use induction here.

(I.e., if $u_k$, $u_{k+1}$ are integers for some $k\in\mathbb Z$, $k\ge 0$, then $u_{k+2}=6u_{k+1}-4u_k$ is also an integer).

Furthermore, $u_n$ is the next integer greater than $(3+\sqrt{5})^n$ because

$3-\sqrt{5}=$

$=\sqrt{3^2}-\sqrt{2^2+1}\in(0,1)$

because more generally for $m\in\mathbb Z$, $m\ge 1$,

$\sqrt{(m+1)^2}=1+\sqrt{m^2}$

$<1+\sqrt{m^2+1}$.

Similar facts are applicable for Pell's equations. See, e.g., this answer.

In this case, you want $x_1=3$, $y_1=1$, $D=5$,

but $3^2-5\cdot 1^2\neq 1$, so a Pell equation isn't easily possible for this sequence, unlike in this one.