7
$\begingroup$

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

$\endgroup$
  • 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
12
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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
9
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.