1

I have this question, we have $a_1,a_2,a_3,\dots$ that is defined as $a_1=4,a_{n+1}=a^2_n-2$ for $n \geq 1$. Show that $y_n=(2+\sqrt{3})^{2^{n-1}}+(2-\sqrt{3})^{2^{n-1}}$ for all positive integers $n \geq 2$.

I guess this is done by induction, but do I need to use the strong version? I have always been confused by inductions. All I can think of when I hear that name is copper wires and magnets. :p

user99468
  • 51

2 Answers2

0

you can let $$a_{1}=x+\dfrac{1}{x}=4,x>1$$ then $$a_{2}=a^2_{1}-2=x^2+\dfrac{1}{x^2}$$ $$a_{3}=a^2_{2}-2=x^{4}+\dfrac{1}{x^4}$$ $$\cdots\cdots\cdots$$ $$a_{n}=x^{2^{n-1}}+\dfrac{1}{x^{2^{n-1}}}$$

math110
  • 93,304
0

We need Strong induction when the recursive definition involves more than previous terms like in Fibonacci, Tribonacci or Tetranacci

But here, if $\displaystyle a_m=(2+\sqrt3)^{2^{m-1}}+(2-\sqrt3)^{2^{m-1}}$

$\displaystyle a_{m+1}=\left((2+\sqrt3)^{2^{m-1}}+(2-\sqrt3)^{2^{m-1}}\right)^2-2$

$\displaystyle = \left((2+\sqrt3)^{2^{m-1}}\right)^2+ \left((2-\sqrt3)^{2^{m-1}}\right)^2+2-2$ as $(2+\sqrt3)(2-\sqrt3)=1$

$$=(2+\sqrt3)^{2^m}+(2-\sqrt3)^{2^m}$$

lab bhattacharjee
  • 274,582
  • Should I not start by testing $m=2$ or something like that? And I maybe got this wrong but is not the strong part that I also test for $m=3$? – user99468 Nov 30 '13 at 11:49
  • @user99468, testing with more than cases including the base case, does not make an induction strong. See the definition in the link in the answer – lab bhattacharjee Nov 30 '13 at 14:09