1
$\begingroup$

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

Can someone please help me with this problem.

  • 0
    Do you know how induction works in general?2012-10-22
  • 1
    **Hint**: linear recurrence relation with constant coefficients. And $(x-(3+\sqrt5))(x-(3-\sqrt5))=x^2-6x+4$.2012-10-22
  • 0
    Yes I do. I just cant seem to solve this question2012-10-22
  • 0
    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.2012-10-22
  • 0
    Ok thank you for telling me that. I probably would have never guessed that, I believe I did it just now.2012-10-23

3 Answers 3

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.$

  • 0
    Oh. I get it now thank you.2012-10-22
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.

0

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

  • 0
    That's a nice solution and probably the cleanest too, but does it use induction?2012-10-23
  • 0
    @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.2012-10-23