Lucas meets Fibonacci

quite simple if u know

Ln = F(n-1)+F(n+1)

hence

Qn= F(n-1)+F(n+1) /Fn

Qn=2F(n-1) /Fn + 1

Qn=2(1/golden ration) + 1 .at inf

hence ANS = sqrt5

用特征根法 由于两个数列的递推式相同，故其特征根相同。 由 $f(n)=f(n-1)+f(n-2)$ 可得特征方程 $x^2=x+1$ ,解得 $x_1=\frac{1-\sqrt5}{2},x_2=\frac{1+\sqrt5}{2}$ 。 可设 $L(n)=a \cdot x_1^n+b \cdot x_2^n \\F(n)=c \cdot x_1^n+d \cdot x_2^n$

将 $L(1)=1,L(2)=3,F(1)=1,F(2)=1$ 代入，解得

$c=-\frac{1}{\sqrt5},d=\frac{1}{\sqrt5} \\ a=1,b=1$

令 $X=x_1^n,Y=x_2^n,t=Y/X$ 则

$Q_n=\frac{a\cdot X+b\cdot Y}{c\cdot X+d\cdot Y}= \frac{a+b\cdot Y/X}{c+d\cdot Y/X}=\frac{a+bt}{c+dt}$ 当 $n\rightarrow \infty$ 时, $t\rightarrow \infty$ 可用 $L'Hospital's\;rule$ ，则 $\lim_{n \to +\infty}Q_n=\lim_{t \to +\infty}\frac{a+bt}{c+dt}=\frac{b}{d}=\sqrt5$ 。

thus the answer is $\sqrt5$

Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

lucas_mem = {1:1, 2:3}
def lucas(n):
    if n in lucas_mem:
        return lucas_mem[n]
    lucas_mem[n] = lucas(n-1) + lucas(n-2)
    return lucas_mem[n]
fib_mem = {1:1, 2:1}
def fib(n):
    if n in fib_mem:
        return fib_mem[n]
    fib_mem[n] = fib(n-1) + fib(n-2)
    return fib_mem[n]
infinity = 1000
# build tables to reduce recursion
for i in xrange(1, infinity):
    lucas(i)
    fib(i)
print lucas(infinity) / float(fib(infinity))