Prove by induction that this number is an integer:



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

  • 3
    $\begingroup$ What did you try ? $\endgroup$ – Claude Leibovici Aug 23 '14 at 4:29
  • $\begingroup$ 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)$ $\endgroup$ – Keith Aug 23 '14 at 4:33
  • 1
    $\begingroup$ @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. $\endgroup$ – Bill Dubuque Aug 23 '14 at 17:34
  • $\begingroup$ Related: math.stackexchange.com/questions/1903099 $\endgroup$ – 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.

  • $\begingroup$ 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})$. $\endgroup$ – Pedro Tamaroff Aug 23 '14 at 4:49
  • 1
    $\begingroup$ @PedroTamaroff: Your comment is clearer than my answer, an example of how greater generality can be simpler. $\endgroup$ – André Nicolas Aug 23 '14 at 4:52
  • $\begingroup$ Does induction holds for $n-1$ ? $\endgroup$ – Keith Aug 23 '14 at 5:04
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Aug 23 '14 at 5:37
  • $\begingroup$ @Pedro Another simple way to view it is via the multiplicativity of conjugation - see my answer. $\endgroup$ – 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,\,\bar\alpha^{\,n} = j \pm k\sqrt{5}\,$ are $\,\color{#c00}{\rm conjugate}\,$ (so their sum $= 2j\in\Bbb Z)$

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

Remark $\ $ Hence we see that the proof is a special case of the inductive extension of the $\color{#0a0}{\textit{multiplicativity}}$ of conjugation, i.e $\ \overline{\alpha_1\cdots \alpha_n}\, =\, \overline\alpha_1\cdots \overline\alpha_n,\,$ in special power case $\,\alpha_i = \alpha$.


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


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



because more generally for $m\in\mathbb Z$, $m\ge 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.