글들.

Project Euler - Problem 2

이전 풀이에 남겨진 박재현 선배의 코멘트를 보고…

Good job! Can you prove this recurrence for only even-valued terms in the Fibonacci sequence? That is, if we let the sequence be a, a0 = 0, a1 = 2, a2 = 8, a3 = 34, …, and so on. The recurrence is this: a0 = 0, a1 = 2, an = a[n-1]*4 + a[n-2] for n >= 2. It’ll be a good exercise on Fibonacci numbers. Good luck!

피보나치 수열 a는 다음과 같이 귀납적으로 정의된다.

a0 = 0, a1 = 1,
a[n] = a[n-1] + a[n-2] (n>=2)

또, 수열 a에서 짝수 값을 갖는 항은

a0 = 0 (even), a1 = 1 (odd)
a2 = a1 + a0 = (odd) + (even) = (odd)
a3 = a2 + a1 = (odd) + (odd) = (even)
a4 = a3 + a2 = (even) + (odd) = (odd)
a5 = a4 + a3 = (odd) + (even) = (odd)
a6 = a5 + a4 = (odd) + (odd) = (even)
...계속.

에 의해서

a[3k] (k는 0 이상인 정수)

뿐이다.

피보나치 수열에서 짝수 값만 가지는 수열*only* even-valued terms in Fibonacci sequence b를 정의해보자. b는 위 내용에 따라서

b[n] = a[3n]

으로 둘 수 있다. 수열 a를 새롭게 풀어보면

b[n] = a[3n]
= a[3n-1] + a[3n-2]
= a[3n-2] + a[3n-3] + a[3n-2]
= 2 * a[3n-2] + a[3n-3]
= 2 * (a[3n-3] + a[3n-4]) + a[3n-3]
= 3 * a[3n-3] + a[3n-4] + a[3n-5] + a[3n-6]
= 4 * a[3n-3] + a[3n-6]
= 4 * b[n-1] + b[n-2]

따라서, 수열 b를 다음과 같이 귀납적으로 정의할 수 있다.

b0 = 0, b1 = 2,
b[n] = 4 * b[n-1] + b[n-2] (n>=2)

근데, 내가 맞게 한건가?