1

Use induction to prove that $(3+ \sqrt 5)^n + (3-\sqrt 5)^n$ is always even.

Can someone please help me with this problem.

Asaf Karagila
  • 393,674
idk
  • 23
  • 4
  • Do you know how induction works in general? – SiliconCelery Oct 22 '12 at 21:48
  • 1
    Hint: linear recurrence relation with constant coefficients. And $(x-(3+\sqrt5))(x-(3-\sqrt5))=x^2-6x+4$. – anon Oct 22 '12 at 21:51
  • Yes I do. I just cant seem to solve this question – idk Oct 22 '12 at 22:07
  • Welcome to MSE @kdeenkid, glad to see you're having good luck so far. Be sure to accept the answer when somebody answers to your questions (the green checkmark by each answer, next to the arrows). It rewards people who help you out. – Alexander Gruber Oct 22 '12 at 22:42
  • Ok thank you for telling me that. I probably would have never guessed that, I believe I did it just now. – idk Oct 23 '12 at 00:32

3 Answers3

10

Hint $\rm\,\ a^{n+2}\! + b^{n+2} = (a\!+\!b)\,(a^{n+1}\!+b^{n+1}) - ab\, (a^n\! + b^n).\ $ Here $\rm\:a\!+\!b = 6,\ ab = 4.$

Or: $ $ note that $\rm\:f(x) + f(-x) = 2\,(f_0 + f_2 x^2 + f_4 x^4 +\cdots\, + f_{2k}\, x^{2k}) =$ twice the even part of $\rm f(x).\:$ Therefore for $\rm\:f(x) = (3+x)^n$ and $\rm\:x = \sqrt{5},\:$ the RHS is an even integer by $\rm\,f_i\in \Bbb Z,\ x^{2i}\! = 5^i\in \Bbb Z.$

Bill Dubuque
  • 272,048
1

Prove by induction that $(3+ \sqrt 5)^n= x_n + y_n \sqrt 5$ for $x_n$ and $y_n$ integers because $x_0=1$ and $y_0=0$ and $x_{n+1}=3x_n+5y_n$, $y_{n+1}=x_n+3y_n$.

Prove by induction that $(3-\sqrt 5)^n=x_n - y_n \sqrt 5$, for the same $x_n$ and $y_n$ as above.

Conclude that $(3+ \sqrt 5)^n + (3-\sqrt 5)^n= 2x_n$, which is an even integer.

lhf
  • 216,483
0

Hint: Binomial Theorem. ${}{}{}$

Gerry Myerson
  • 179,216
  • That's a nice solution and probably the cleanest too, but does it use induction? – lhf Oct 23 '12 at 01:01
  • @lhf, good point. I suppose I could say that induction is used in the proof of the Binomial Theorem, but that is a bit of a cheat. – Gerry Myerson Oct 23 '12 at 05:09