1

Prove $(1+\sqrt 2)^n - (1-\sqrt 2)^n$ is divisible by $2$ for all integers $n\ge0$

I am trying to prove this by induction and having a hard time doing so. What I have for the inductive step is $$(1+\sqrt 2)^{k+1} - (1-\sqrt 2)^{k+1}$$ then $$(1+\sqrt 2)(1+\sqrt 2)^k - (1-\sqrt 2)(1-\sqrt 2)^k$$

I do not know where to go from here.

lulu
  • 70,402
enchantingcedarfog
  • 19
  • 1
  • 3
    I think there's a typo, shouldn't that be a plus between them? Otherwise trivially $n = 1$ fails this because the result isn't even an integer. Also, if this is the case then you may find it easier to prove this directly using the binomial theorem. – Stephen Donovan Apr 30 '21 at 22:56
  • 3
    Or, alternatively, he forgot to divide by $2^{1/2}$ instead of a plus sign. – LPenguin Apr 30 '21 at 23:00
  • 1
    $a_n=(1+\sqrt 2)^n +(1-\sqrt 2)^n$ satisfy a recursion where each element can be expressed as a linear combination of the previous two – J. W. Tanner Apr 30 '21 at 23:00
  • @enchantingcedarfog could you clarify the statement? – pancini Apr 30 '21 at 23:17
  • 1
    Or it's possible that it means $(1 + \sqrt{2})^n - (1 - \sqrt{2})^n$ is in the ideal $\langle 2 \rangle$ of the ring $\mathbb{Z}[\sqrt{2}]$. (Though that seems like a less likely possibility than the others.) – Daniel Schepler Apr 30 '21 at 23:33
  • Also all integers $n<0$ maybe? – Oscar Lanzi May 01 '21 at 00:24

2 Answers2

1

Hint

$$[(1+\sqrt{2})^{k} - (1-\sqrt{2})^{k}][(1+\sqrt{2})+(1-\sqrt{2})]=$$ $$=[(1+\sqrt{2})^{k+1} - (1-\sqrt{2})^{k+1}]-(1-\sqrt{2})^{k}(1+\sqrt{2})+(1+\sqrt{2})^{k}(1-\sqrt{2})$$ $$=[(1+\sqrt{2})^{k+1} - (1-\sqrt{2})^{k+1}]-[(1+\sqrt{2})^{k-1} - (1-\sqrt{2})^{k-1}]$$

To be clear, if you call $a_k=(1+\sqrt{2})^{k} - (1-\sqrt{2})^{k}$, the above equality means,

$$2a_k=a_{k+1}-a_{k-1}\Leftrightarrow a_{k+1}=2a_k+a_{k-1}.$$

Can you finish?

Arnaldo
  • 21,342
0

Statement: prove that for any $n \ge 1$, $(1+\sqrt{2})^n + (1-\sqrt{2})^n$ is divisible by $2$. ( Note we can start with $n = 1$ and that the sign of $+$ is used as the original statment by OP is wrong if the $-$ sign is used. )

Claim 2: For any $k \ge 1, \exists m \ge 1: (1+\sqrt{2})^k - (1-\sqrt{2})^k= m\sqrt{2}, k, m \in \mathbb{N}$ .

Proof: $k = 1 \implies m = 2$. Assume assertion is true for $k$, we show it's trur for $k+1$. Indeed, $(1+\sqrt{2})^{k+1} - (1-\sqrt{2})^{k+1}= (1+\sqrt{2})(1+\sqrt{2})^k-(1-\sqrt{2})(1-\sqrt{2})^k= (1+\sqrt{2})^k -(1-\sqrt{2})^k +\sqrt{2}((1+\sqrt{2})^k + (1-\sqrt{2})^k)= c\sqrt{2}+\sqrt{2}\cdot p= (c+p)\sqrt{2}, c, p\in \mathbb{N}$.

Claim 1: for all $n \ge 1, (1+\sqrt{2})^n + (1-\sqrt{2})^n$ is an integer.

Proof: $n = 1$ is clear as $2$ is an integer. Assume it's true for up to $n$. We show it's true for $n+1$. Indeed, $(1+\sqrt{2})^{n+1} + (1-\sqrt{2})^{n+1}= 2((1+\sqrt{2})^n + (1-\sqrt{2})^n)+ ((1+\sqrt{2})^{n-1}+(1-\sqrt{2})^{n-1}) = 2e+f$ which is an integer since $e,f$ are integers by inductive step. Thus the claim is true for all $n$.

Return to your inductive step above: $(1+\sqrt{2})^{k+1}+(1-\sqrt{2})^{k+1}= (1+\sqrt{2})^k+(1-\sqrt{2})^k+\sqrt{2}((1+\sqrt{2})^k - (1-\sqrt{2})^k)= 2d+\sqrt{2}(s\sqrt{2})= 2d+2s= 2(d+s)$ which is divisible by $2$. Thus by induction we're done.

Note: in doing this proof,we use the following identity: $a^{n+1}+b^{n+1} = (a+b)(a^n+b^n) - ab(a^{n-1}+b^{n-1})$. Apply this for $a = 1+\sqrt{2}, b = 1 - \sqrt{2}$ to get the identity in the proof of claim 1.