# Help proving a recursively defined sequence

Prove that the sequence $\frac{(1+\sqrt{2})^n(1-\sqrt{2})^n}{2\sqrt2}$ = $a_n$, where $a_0$ = 0, $a_1$ = 1, $a_2$ = 2, $a_3$ =5, $a_4$ = 12, and $a_5$ = 29 ( according to the function $a_n$ = 2( $a_{n-1})$ + ( $a_{n-2}$))

The question gives us a hint to use the solutions $x^2$ =$2x+1$.

Using the hint, I understood the the solutions to $x^2 - 2x -1$ are the two equations inclosed in the two top brackets of the sequences' numerator. Not sure on what to do with this information to prove the function.

I would personally assume to plug in the 1 to 5 as n in the sequence and prove that both $a_n$ functions equal each other. But that seems too easy.

My question is how do I use the information I gained from the hint to prove the function?

• @angryavian links back to my question? – MuthuShank Oct 19 '17 at 19:42
• You obviously have miscopied the sequence formula, as $$\frac{(1+\sqrt 2)^n(1-\sqrt 2)^n}{2\sqrt 2} = \frac{((1+\sqrt 2)(1-\sqrt 2))^n}{2\sqrt 2} = \frac{(-1)^n}{2\sqrt 2}$$ which is not integer for any power of $n$. – Paul Sinclair Oct 19 '17 at 23:27
• I'm pretty sure the two $n$th powers in the numerator should be subtracted from each other, not multiplied. – Henning Makholm Oct 19 '17 at 23:46
• @MuthuShank Sorry, here is the link I intended: math.stackexchange.com/questions/1068367/… – angryavian Oct 20 '17 at 1:46

## 1 Answer

Note that if $b = 1 + \sqrt 2, c = 1 - \sqrt 2$, then the sequences $\{b^n\}_{n=1}^\infty$ and $\{c^n\}_{n=1}^\infty$ both satisfy the same recursion: Since $b^2 = 2b + 1$ (as a solution to the quadratic), if you multiply through by $b^{n-2}$, you get the desired recursion $$b^n = 2b^{n-1} + b^{n-2}$$ and similarly for $c^n$.

But of course, neither sequence satisfies the starting conditions $a_0 = 0, a_1 = 1$, so neither one of them is $\{a_n\}$. But suppose you try $$a_n := Bb^n + Cc^n$$ for some constants $B, C$.

Can you prove that if $\{a_n\}$ is defined this way, it must also satisfy $a_n = 2a_{n-1} + a_{n-2}$? And can you figure out values for $B$ and $C$ so that $a_0 = 0$ and $a_1 = 1$?

The resulting formula will not be the one you posted (which does not work), but will be the one that was intended.