Why is $(N+\sqrt{N^2-1})^k + (N+\sqrt{N^2-1})^{-k}$ the solution to the recurrence sequence $ x_n=x_{n-1} + x_{n-2}$

Question

May I know why is that so? Because I was trying to prove $(N+\sqrt{N^2-1})^k$, where k is a positive integer, differs from the integer nearest to it by less than $(2N-\frac{1}{2})^{-k}$. I checked the answer, and it said that $(N+\sqrt{N^2-1})^k + (N+\sqrt{N^2-1})^{-k}$ is the solution to the recurrence sequence, with $x_0 =2, x_1 =2N$. Hence, it is an integer. So$(N+\sqrt{N^2-1})>2N-\frac{1}{2} $.

Could you guys pls explain why is that so to me?

Thank you very much for your reply

This appears to be the famous Fibonacci sequence. Search for that and you will find a lot of material. — badjohn, Jan 14 '20 at 09:55

score 3 · Accepted Answer · answered Jan 14 '20 at 10:35

3

The claim in the title is false: $(N+\sqrt{N^2-1})^k + (N+\sqrt{N^2-1})^{-k}$ satisfies $x_{k+2}=2N x_{k+1} - x_k$.

In general, $x_k=a^k+b^k$ satisfies $x_{k+2}=(a+b) x_{k+1} - (ab) x_k$.

answered Jan 14 '20 at 10:35

lhf

216,483

Thank you, could you prove the question for me? I really have no clue on how to do this. Thank you very much. – Henry Cai Jan 14 '20 at 12:14
@HenryCai, try induction. – lhf Jan 14 '20 at 12:24

Why is $(N+\sqrt{N^2-1})^k + (N+\sqrt{N^2-1})^{-k}$ the solution to the recurrence sequence $ x_n=x_{n-1} + x_{n-2}$

1 Answers1