뤼카 수열

뤼카 수열(Lucas sequence)은 일차 점화식으로 정의되는 수열로, 첫 두 항이 독립 변수이고 그 다음 항부터 이전 두 항의 일차결합 형태로 나아간다. 피보나치 수열의 확장판이라 할 수 있다.

뤼카 수

뤼카 수(Lucas number)는 아래 점화식으로 정의된다.

• [math]\displaystyle{ L_0=2, L_1=1 }[/math]
• [math]\displaystyle{ L_{n+2}=L_{n+1}+L_n }[/math]

참고로 피보나치 수 [math]\displaystyle{ \{F_n\} }[/math]의 경우 [math]\displaystyle{ F_0=0, F_1=1 }[/math]에서 출발하며 점화식은 동일하다.

0번째 항부터 처음 항들을 나열하면

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, …

이다.

항의 번호를 음의 정수로도 확장하면 점화식을 [math]\displaystyle{ L_{n-2}=L_n-L_{n-1} }[/math]과 같이 변형할 수 있다. 2는 여전히 0번째 항이다.

… 18, -11, 7, -4, 3, -1, 2, 1, 3, 4, 7, 11, 18, …

피보나치 수와의 관계

점화식을 풀면 아래와 같이 나타낼 수 있다. [math]\displaystyle{ \phi=\frac{1+\sqrt{5}}{2}, \psi=\frac{1-\sqrt{5}}{2} }[/math]이며, [math]\displaystyle{ \phi+\psi=1, \phi\psi=-1 }[/math]이다.

• [math]\displaystyle{ F_n=\frac{\phi^n-\psi^n}{\phi-\psi}, L_n=\phi^n+\psi^n }[/math]

두 수열의 이웃한 항끼리의 비는 항이 커짐에 따라 황금비에 가까워진다. 음의 방향으로는 황금비에 마이너스 부호가 딸려 나온다.

• [math]\displaystyle{ \lim_{n \to \infty}\frac{F_{n+1}}{F_n}=\lim_{n \to \infty}\frac{L_{n+1}}{L_n}=\phi }[/math]
• [math]\displaystyle{ \lim_{n \to -\infty}\frac{F_{n-1}}{F_n}=\lim_{n \to -\infty}\frac{L_{n-1}}{L_n}=\psi^{-1}=-\phi }[/math]

또한 항 번호가 음의 정수일 때, 두 수열은 홀수 번째, 짝수 번째 항의 부호 교대가 거꾸로 나타난다.

• [math]\displaystyle{ L_{-n}=(-1)^n L_n, F_{-n}=-(-1)^n F_n }[/math]

만약 점화식은 동일하고, 초기 조건이 [math]\displaystyle{ a_0=u, a_1=v }[/math]로 주어졌을 때, 이 수열은 위 두 수열의 일차결합으로 표현할 수 있다.

• [math]\displaystyle{ a_n=\frac{u}{2}L_n+\left(v-\frac{u}{2}\right)F_n }[/math]

그 밖에 아래와 같은 성질들이 있다.

• [math]\displaystyle{ L_n=F_{n-1}+F_{n+1}, F_n=\frac{L_{n-1}+L_{n+1}}{5} }[/math]
• [math]\displaystyle{ L_{m+n}=\frac{L_mL_n+5F_mF_n}{2} }[/math]
• [math]\displaystyle{ L_{2n}=L_n^2-2(-1)^n=5F_n^2+2(-1)^n }[/math]
• [math]\displaystyle{ F_{m+n}=\frac{F_mL_n+L_mF_n}{2} }[/math]
• [math]\displaystyle{ F_{2n}=L_nF_n }[/math]

뤼카 수열

위의 점화식을 일반적인 일차결합으로 확장할 수 있다. 일반화된 뤼카수열에는 제1종과 2종이 있다.

• 제1종 뤼카 수열: [math]\displaystyle{ U_0(P, Q)=0, U_1(P, Q)=1, U_{n+2}(P, Q) =P\cdot U_{n+1}(P, Q)-Q\cdot U_n(P, Q) }[/math]
• 제2종 뤼카 수열: [math]\displaystyle{ V_0(P, Q)=2, V_1(P, Q)=P, V_{n+2}(P, Q) =P\cdot V_{n+1}(P, Q)-Q\cdot V_n(P, Q) }[/math]

이 점화식을 풀면 아래와 같이 표현된다. [math]\displaystyle{ \alpha, \beta }[/math]는 방정식 [math]\displaystyle{ x^2+Px+Q=0 }[/math]의 해이다.

• [math]\displaystyle{ \alpha=\frac{P+\sqrt{P^2-4Q}}{2}, \beta=\frac{P-\sqrt{P^2-4Q}}{2} }[/math]
• [math]\displaystyle{ U_n(P, Q)=\frac{\alpha^n-\beta^n}{\alpha-\beta} }[/math]
• [math]\displaystyle{ V_n(P, Q)=\alpha^n+\beta^n }[/math]

성질

이들 수열의 성질은 앞서 소개한 [math]\displaystyle{ F_n, L_n }[/math]과 비슷한 모양으로 쓸 수 있다. 단, [math]\displaystyle{ D=(\alpha-\beta)^2=P^2-4Q }[/math]이며, 표기의 편의를 위해 [math]\displaystyle{ U_n(P, Q)=U_n, V_n(P, Q)=V_n }[/math]으로 쓴다.

• [math]\displaystyle{ V_n=U_{n-1}-QU_{n+1}, U_n=\frac{V_{n-1}-QV_{n+1}}{D} }[/math]
• [math]\displaystyle{ V_{m+n}=\frac{V_mV_n+DU_mU_n}{2} }[/math]
• [math]\displaystyle{ V_{2n}=V_n^2-2Q^n=DU_n^2+2Q^n }[/math]
• [math]\displaystyle{ U_{m+n}=\frac{U_mV_n+V_mU_n}{2} }[/math]
• [math]\displaystyle{ U_{2n}=V_nU_n }[/math]

특수한 뤼카 수열

• [math]\displaystyle{ P=1, Q=-1 }[/math]: 이 경우 피보나치 수 및 뤼카 수와 같다. [math]\displaystyle{ U_n(1, -1)=F_n, V_n(1, -1)=L_n }[/math]
• [math]\displaystyle{ P=2, Q=-1 }[/math]: [math]\displaystyle{ U_n(2, -1)=\frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2\sqrt{2}} }[/math]은 펠 수이며, [math]\displaystyle{ V_n(2, -1)=(1+\sqrt{2})^n+(1-\sqrt{2})^n }[/math]은 펠-뤼카 수이다.
• [math]\displaystyle{ P=3, Q=2 }[/math]: [math]\displaystyle{ U_n(3, 2)=2^n-1 }[/math]은 메르센 수와 같다. [math]\displaystyle{ V_n(3, 2)=2^n+1 }[/math]의 경우 [math]\displaystyle{ n=2^k }[/math]이면 이 수는 페르마 수가 된다.
• [math]\displaystyle{ P=1, Q=-2 }[/math]: [math]\displaystyle{ U_n(1, -2)=\frac{2^n-(-1)^n}{3} }[/math]의 홀수 번째 항은 와그스태프 수와 같다.
• [math]\displaystyle{ P=4, Q=1 }[/math]: [math]\displaystyle{ V_n(4, 1)=(2+\sqrt{3})^n+(2-\sqrt{3})^n }[/math]에서 [math]\displaystyle{ r_k=V_{2^k}(4, 1) }[/math]은 뤼카-레머 소수판정법에 쓰이는 수열이다.

같이 보기

• 피보나치 수열
• 피보나치 소수, 뤼카 소수
• 황금비, 금속비