Prove $(1+\sqrt 2)^n - (1-\sqrt 2)^n$ is divisible by $2$ for all integers $n\ge0$ 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.
 A: 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?
A: 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.
