Prove by induction that $\left [ \left (3+\sqrt{5} \right )^{n} + \left (3-\sqrt{5} \right )^{n} \right ]$ is multiple of $2^{n}$

Question

Prove by induction that :

$\left [ \left (3+\sqrt{5} \right )^{n} + \left (3-\sqrt{5} \right )^{n} \right ]$ is multiple of $ 2^{n}$

My proof is :

At $n=1$

$$\frac{\left ( 3+\sqrt{5} \right )+\left ( 3-\sqrt{5} \right )}{2} = \frac{6}{2} = 3 \in \mathbb{Z}$$

Assume $P(k)$ is true

$$\frac{\left ( 3+\sqrt{5} \right )^{k}+\left ( 3-\sqrt{5} \right )^{k}}{2^{k}} = m \in \mathbb{Z}$$

$$\Rightarrow \left ( 3+\sqrt{5} \right )^{k}+\left ( 3-\sqrt{5} \right)^{k} = 2^{k}.m \rightarrow (*)$$

At $n=k+1$

$$\left ( 3+\sqrt{5} \right )^{k+1}+\left ( 3-\sqrt{5} \right )^{k+1} = \left [ \left ( 3+\sqrt{5} \right )^{k}+\left ( 3-\sqrt{5} \right )^{k} \right ]\left [ \left ( 3+\sqrt{5} \right )+\left ( 3-\sqrt{5} \right ) \right ]-\left [ \left ( 3+\sqrt{5} \right )^{k}\left ( 3-\sqrt{5} \right )+\left ( 3-\sqrt{5} \right )^{k}\left ( 3+\sqrt{5} \right ) \right ]$$

from $(*) $:

$$\left ( 3+\sqrt{5} \right )^{k+1}+\left ( 3-\sqrt{5} \right )^{k+1} =2^{k}.m.6-\left ( 3+\sqrt{5} \right )\left ( 3-\sqrt{5} \right ) \left [ \left ( 3+\sqrt{5} \right )^{k-1}+\left ( 3-\sqrt{5} \right )^{k-1} \right ] $$

but i can't resume my proof .. i can't do any thing with $\left [ \left ( 3+\sqrt{5} \right )^{k-1}+\left ( 3-\sqrt{5} \right )^{k-1} \right ]$ .

Answer 1

Another way to solve this problem is to define $a_n = (3 + \sqrt{5})^n + (3-\sqrt{5})^n$ and note that the characteristic equation of this sequence is $x^2 - 6x + 4 = 0$. Therefore $a_{n+2} = 6a_{n+1} - 4a_n$

Obviously we have that $2 \mid a_1$ and $4 \mid a_2$. Now assume that $2^n \mid a_n$ for all $n \le k$ for some integer $k$. Then we have:

$$2^{k+1} \mid 6a_{k} - 4a_{k-1} = a_{k+1}$$

Hence the proof.

Answer 2

You're on the right track, but you need to use a slightly extended form of induction for this problem. Note that to prove $P(k+1)$, you don't have to limit yourself to $P(k)$; you can also use $P(i)$ for $i\leq k$. In this case, the proposition $P(k-1)$ will prove helpful for dealing with the last term. (But note that this means that you're going to have to prove two base cases, rather than just one!)

To be a little more explicit, let's write $s_n=(3+\sqrt{5})^n+(3-\sqrt{5})^n$. Then the relation that you've discovered is that $s_{k+1}=6s_k-4s_{k-1}$. (Note that you have a small mistake where you write $2^k\cdot m\cdot 4$; that $4$ should be a $6$, because it's $(3+\sqrt5)+(3-\sqrt5)$. The $4$ in the second term here arises as the product $(3+\sqrt5)\cdot(3-\sqrt5)$.) Now, we know that there are $a$ and $b$ such that $s_k=a\cdot 2^k$ and $s_{k-1}=b\cdot 2^{k-1}$; what does the relation then say about $s_{k+1}$?

Answer 3

An idea for you assuming the claim's true for exponents up to $\;k\;$ . Observe that I begin from the middle of your work:

$$\left ( 3+\sqrt{5} \right )^{k+1}+\left ( 3-\sqrt{5} \right )^{k+1} = \left [ \left ( 3+\sqrt{5} \right )^{k}+\left ( 3-\sqrt{5} \right )^{k} \right ]\left [ \left ( 3+\sqrt{5} \right )+\left ( 3-\sqrt{5} \right ) \right ]-$$

$$-\left [ \left ( 3+\sqrt{5} \right )^{k}\left ( 3-\sqrt{5} \right )+\left ( 3-\sqrt{5} \right )^{k}\left ( 3+\sqrt{5} \right ) \right ]=$$

$$=2^km\cdot6-(3+\sqrt5)(3-\sqrt5)\overbrace{\left[(3+\sqrt5)^{k-1}+(3-\sqrt5)^{k-1}\right]}^{=2^{k-1}\cdot r\,,\,\,r\in\Bbb Z}=$$

$$=2^{k+1}\cdot3m-(9-5)\cdot2^{k-1}\cdot r=2^{k+1}(3m+r).\;\;\;\;\;\square$$