피보나치 수열 심화과정5 -피보나치 수열의 합을 가장 빠르게 구하는 방법-

1. 피보나치 수열

 

$F_{0} = 0, F_{1} = 1, F_{n} = F_{n-1}+F_{n-2}, n \geq 2$로 정의되는 수열 $F_{n}$

 

 

2. 홀수번째 항의 합

 

1항부터 $2n-1$번째 항까지의 합은 다음과 같이 $2n$번째 항과 동일하다.

 

$$\sum_{k = 1}^{n} F_{2k-1} = F_{2n}$$

 

 

증명)

 

$F_{n+2} = F_{n+1} + F_{n}$에서 n = 2n - 2를 대입하면, $F_{2n} = F_{2n-1} + F_{2n-2}$

 

그러면, $F_{2n-1} = F_{2n} - F_{2n-2}$이므로,

 

$$\sum_{k=1}^{n} F_{2k-1} = F_{1} + \sum_{k=2}^{n} (F_{2k} - F_{2k-2})$$

 

이 식을 풀어서 써보면, 망원급수임을 알 수 있다. 즉,

 

$$F_{1} + (F_{4} - F_{2}) + (F_{6} - F_{4}) + .... + (F_{2n-2} - F_{2n-4}) + (F_{2n} - F_{2n-2}) = F_{1} - F_{2} + F_{2n} = 1 - 1 + F_{2n} = F_{2n}$$

 

그러므로 $$\sum_{k=1}^{n} F_{2k-1} = F_{2n}$$

 

 

3. 연습문제1

 

11442번: 홀수번째 피보나치 수의 합 (acmicpc.net)

11442번: 홀수번째 피보나치 수의 합

 

위 식을 이용해서 n을 2n-1번째라고 생각하고 2n번째 피보나치 항을 구하면 된다.

 

예를 들어 n = 10이 주어진다면?

 

1,3,5,7,9번째 항의 합이고, 이 때 n = 5이고 2n = 10번째 피보나치 항을 구하면 된다.

 

n = 7이 주어진다면?

 

1,3,5,7번째 항의 합을 구해야하고, n = 4이고 2n = 8번째 피보나치 항을 구하면 된다.

 

n의 범위가 매우 크기때문에, 행렬을 이용해 로그 시간에 피보나치 수열의 항을 구해야한다

 

#1항부터 2n-1번째 항까지의 홀수번째 피보나치 수열의 합
from sys import stdin

mod = 1000000007

def matrix_multiplication(a,b,mod):
    
    result = [[0,0],[0,0]]

    for i in range(2):
        
        for j in range(2):
            
            for k in range(2):
                
                result[i][j] += a[i][k]*b[k][j]
                result[i][j] %= mod
    
    return result

def matrix_exponentiation(matrix,n,mod):
    
    result = [[1,0],[0,1]]

    while n > 0:
        
        if n % 2 == 1:
            
            result = matrix_multiplication(result,matrix,mod)
        
        matrix = matrix_multiplication(matrix,matrix,mod)

        n //= 2
    
    return result

#1항부터 2n-1번째 항의 합은, 2n번째 항과 같다.
n = int(stdin.readline())

n = (n+1)//2

matrix = [[1,1],[1,0]]

result = matrix_exponentiation(matrix,2*n,mod)

print(result[1][0])

 

4. 짝수번째 항의 합

 

1번째 항부터 $2n$번째 항의 합은, $2n+1$번째 항에 1을 뺀 값과 같다.

 

$$\sum_{k = 1}^{n} F_{2k} = F_{2n+1} - 1$$ 

 

 

증명)

 

$F_{n+2} = F_{n+1} + F_{n}$에서, n 대신에 2n-1을 대입하면 $F_{2n+1} = F_{2n} + F_{2n-1}$이다.

 

즉, $F_{2n} = F_{2n+1} - F_{2n-1}$이므로, $\sum_{k=1}^{n} F_{2k} = \sum_{k=1}^{n} (F_{2k+1} - F_{2k-1})$

 

이 식을 풀어써보면, 망원급수임을 알 수 있다. 즉,

 

$$F_{3} - F_{1} + F_{5} - F_{3} + F_{7} - F_{5} + ... + F_{2n-1} - F_{2n-3} + F_{2n+1} - F_{2n-1} = F_{2n+1} - F_{1} = F_{2n+1} - 1$$

 

그러므로, $\sum_{k=1}^{n} F_{2k} = F_{2n+1} - 1$

 

 

5. 연습문제2

 

11443번: 짝수번째 피보나치 수의 합 (acmicpc.net)

11443번: 짝수번째 피보나치 수의 합

 

n이 주어질때, 2n으로 보고 2n+1번째 피보나치 항을 구한 다음에 1을 빼면 된다.

 

즉 n = 7이 주어지면 2,4,6번째 항의 합을 구해야하니 n = 3이다. 그러므로 2n+1 = 7번째 항에 1을 빼면 된다.

 

n = 10이 주어지면 2,4,6,8,10번째 항의 합을 구해야하니 n = 5이다. 그러므로 2n+1 = 11번째 항에 1을 빼면 된다.

 

역시 n의 범위가 매우 크므로 행렬을 이용해 로그 시간에 피보나치 항을 구해줘야한다.

 

#1항부터 2n번째 항까지 짝수번째 피보나치 수열의 합
from sys import stdin

mod = 1000000007

def matrix_multiplication(a,b,mod):
    
    result = [[0,0],[0,0]]

    for i in range(2):
        
        for j in range(2):
            
            for k in range(2):
                
                result[i][j] += a[i][k]*b[k][j]
                result[i][j] %= mod
    
    return result

def matrix_exponentiation(matrix,n,mod):
    
    result = [[1,0],[0,1]]

    while n > 0:
        
        if n % 2 == 1:
            
            result = matrix_multiplication(result,matrix,mod)
        
        matrix = matrix_multiplication(matrix,matrix,mod)

        n //= 2
    
    return result
    
#1항부터 2n번째 항까지 합 2,4,6,8,...,2n번째 피보나치 합은 2n+1번째 항 - 1과 같다.

n = int(stdin.readline())//2

matrix = [[1,1],[1,0]]

result = matrix_exponentiation(matrix,2*n+1,mod)

print(result[1][0]-1)

 

 

6. 모든 항의 합

 

피보나치 수열의 1번째 항부터 $n$번째 항까지의 합은, $n+2$번째 항에 1을 뺀 값과 같다.

 

$$\sum_{k = 1}^{n} F_{k} = F_{n+2} - 1$$

 

 

증명)

 

$F_{n+2} = F_{n} + F_{n+1}$이므로, $F_{n} = F_{n+2} - F_{n+1}$이다.

 

그러므로, $$\sum_{k=1}^{n} F_{k} = \sum_{k = 1}^{n} F_{k+2} - F_{k+1}$$

 

이 식을 풀어쓰면 역시 망원급수임을 알 수 있다.

 

$$F_{3} - F_{2} + F_{4} - F_{3} + F_{5} - F_{4} + ... + F_{n+1} - F_{n} + F_{n+2} - F_{n+1} = F_{n+2} - F_{2} = F_{n+2} - 1$$

 

그러므로, $\sum_{k=1}^{n} F_{k} = F_{n+2} - 1$

 

 

7. 연습문제3

 

2086번: 피보나치 수의 합 (acmicpc.net)

2086번: 피보나치 수의 합

 

a번째 항부터 b번째 항까지의 합은, b번째 항까지의 합에 a-1번째 항까지의 합을 빼면 될 것이다.

 

그러므로 (b+2번째 항 - 1) - (a+1번째 항 - 1)과 같을 것이다.

 

그런데 문제는 modulo exponentiation을 하기 때문에, (b+2번째 항)이 (a+1번째 항)보다 작을 수 있다.

 

무슨 말이냐면 1부터 나열한 수열은..

 

1,2,3,4,5,6,7,8,9,10,11,12,13,14,....에서 각 항을 10으로 나눈 나머지를 나열한 수열

 

1,2,3,4,5,6,7,8,9,0,1,2,3,4,..이 되는데..

 

실제 10번째 항은 10으로 1번째 항 1보다 더 큼에도 불구하고 나머지로 나타내면 0이 되어 1보다 작아진다

 

이런 경우 어떻게 처리해야할까?

 

구체적으로 (b - a) % mod = c일때, c가 음수라면?

 

합동식의 성질에 따라 양변에 mod를 더하고 다시 mod로 나눠주면 된다.

 

((b - a) % mod + mod) % mod = (c + mod) % mod

 

c + mod도 음수일 수 있잖아요?

 

(b-a)%mod가 c이기 때문에, c의 절댓값은 mod를 넘을 수 없다. 

 

 

#피보나치 수열의 합
from sys import stdin

def matrix_multiplication(a,b,mod):
    
    result = [[0,0],[0,0]]

    for i in range(2):
        
        for j in range(2):
            
            for k in range(2):
                
                result[i][j] += a[i][k]*b[k][j]
                result[i][j] %= mod
    
    return result

def matrix_exponentiation(matrix,n,mod):
    
    result = [[1,0],[0,1]]

    while n > 0:
        
        if n % 2 == 1:
            
            result = matrix_multiplication(result,matrix,mod)
        
        matrix = matrix_multiplication(matrix,matrix,mod)
        
        n //= 2
    
    return result

#피보나치 수열의 n번째 항까지의 합은, n+2번째 항에 1을 뺀 값과 같다.
mod = 1000000000

a,b = map(int,stdin.readline().split())

matrix = [[1,1],[1,0]]

sum_a = matrix_exponentiation(matrix,a+1,mod)

sum_b = matrix_exponentiation(matrix,b+2,mod)

print((sum_b[1][0] - sum_a[1][0] + mod) % mod)

 

8. 피보나치 수의 제곱의 합

 

1항부터 n항 각각을 제곱하여 합하면, n번째 항과 n+1번째 항을 곱한것과 같다.

 

$$\sum_{k = 1}^{n} F_{k}^{2} = F_{n}F_{n+1}$$

 

 

증명)

 

$F_{n+1} = F_{n} + F_{n-1}$에서, $F_{n} = F_{n+1} - F_{n-1}$이다.

 

그러므로, $\sum_{k = 1}^{n} F_{k}^{2} = F_{1}^{2} + \sum_{k=2}^{n} F_{k}F_{k}$에서,

 

$F_{1}^{2} + \sum_{k=2}^{n} F_{k}(F_{k+1} - F_{k-1}) = F_{1}^{2} + \sum_{k=2}^{n} F_{k}F_{k+1} - F_{k}F_{k-1}$ 

 

이 식을 풀어써보면, 망원급수임을 알 수 있다.

 

$$F_{1}^{2} + F_{2}F_{3} - F_{2}F_{1} + F_{3}F_{4} - F_{3}F_{2} + F_{4}F_{5} - F_{4}F_{3} + ... F_{n}F_{n+1} - F_{n}F_{n-1} = F_{1}^{2} - F_{2}F_{1} + F_{n}F_{n+1} = F_{n}F_{n+1}$$

 

그러므로, $\sum_{k=1}^{n} F_{k}^{2} = F_{n}F_{n+1}$

 

 

9. 연습문제4

 

11440번: 피보나치 수의 제곱의 합 (acmicpc.net)

11440번: 피보나치 수의 제곱의 합

 

 

 

위 내용을 그대로 구현하면 된다. 

 

n번째 항과 n+1번째 항의 곱을 구한다.

 

주의할 점은 n번째 항과 n+1번째 항을 modulo exponentiation으로 구해서 mod보다 작아짐에도 불구하고,

 

둘을 곱하면 mod보다 커질 수 있기 때문에, 다시 mod로 나눈 나머지를 구해줘야 한다.

 

https://deepdata.tistory.com/869

피보나치 수열 심화과정4 -피보나치 수의 최대공약수 놀라운 성질-

 

그리고 피보나치 수열의 행렬 표현

 

$$\begin{pmatrix}
F_{n+1} & F_{n}\\
F_{n} & F_{n-1}
\end{pmatrix}=\begin{pmatrix}
1 & 1\\
1 & 0
\end{pmatrix}^{n}$$

 

으로부터, (1,0) 원소가 $F_{n}$임을 익히 알고 있는데,

 

(0,0)원소가 $F_{n+1}$이기 때문에, 단 1번만 행렬곱을 구하면 $F_{n}, F_{n+1}$을 모두 구할 수 있다.

 

 

#피보나치 수열 각 항의 제곱의 합
from sys import stdin

mod = 1000000007

def matrix_multiplication(a,b,mod):
    
    result = [[0,0],[0,0]]

    for i in range(2):
        
        for j in range(2):
            
            for k in range(2):
                
                result[i][j] += a[i][k]*b[k][j]
                result[i][j] %= mod
    
    return result

def matrix_exponentiation(matrix,n,mod):
    
    result = [[1,0],[0,1]]

    while n > 0:
        
        if n % 2 == 1:
            
            result = matrix_multiplication(result,matrix,mod)
        
        matrix = matrix_multiplication(matrix,matrix,mod)
        n //= 2
    
    return result

#피보나치 수열의 n번째 항까지 제곱의 합은, n번째 항과 n+1번째 항의 곱과 같다
n = int(stdin.readline())

matrix = [[1,1],[1,0]]

result = matrix_exponentiation(matrix,n,mod)

#(0,0)이 n+1번째 항, (1,0)이 n번째 항이다
print((result[0][0]*result[1][0])%mod)