18강에서 등차수열과 등비수열의 일반항을 구했습니다. 그때 쓴 방법은 "차가 일정하니 d d n − 1 n − 1
이 강의는 답을 만드는 방법을 다룹니다. 앞 항으로 다음 항을 정하는 식을 점화식이라고 하고, n n
이 강의로 S2가 끝납니다. 그리고 여기서 만든 도구는 33강의 수열의 극한에서 곧바로 쓰입니다. 닫힌 형태가 있어야 n n
점화식과 닫힌 형태의 차이를 계산량으로 설명할 수 있습니다.
a n + 1 = p a n + q a n + 1 = p a n + q a n + 1 = a n + f ( n ) a n + 1 = a n + f ( n ) 이차 선형 점화식을 특성방정식으로 풀 수 있습니다.
특성방정식이 중근이나 허근을 가질 때를 판정하고 처리할 수 있습니다.
문제. 수열 a 1 = 3 a 1 = 3 a n + 1 = a n + 4 a n + 1 = a n + 4 a 5 a 5 a 1000 a 1 0 0 0 a n a n n n a 1000 a 1 0 0 0
생각의 실마리. (2)에서 계산 횟수를 세어 봅니다. 점화식은 앞 항을 알아야 다음 항을 구할 수 있으므로 건너뛸 수 없습니다. (3)에서는 a 1 a 1 a n a n 4 4
풀이. (1) 차례로 계산합니다.
a 2 = 7 , a 3 = 11 , a 4 = 15 , a 5 = 19 a 2 = 7 , a 3 = 1 1 , a 4 = 1 5 , a 5 = 1 9
(2) a 1000 a 1 0 0 0 a 2 a 2 a 1000 a 1 0 0 0 999 9 9 9
(3) a 1 a 1 a n a n 4 4 n − 1 n − 1
a n = 3 + 4 ( n − 1 ) = 4 n − 1 a n = 3 + 4 ( n − 1 ) = 4 n − 1
이 식으로는 a 1000 = 4000 − 1 = 3999 a 1 0 0 0 = 4 0 0 0 − 1 = 3 9 9 9
이 문제에서 배우는 것: 점화식과 닫힌 형태.
앞의 항으로 다음 항을 정하는 식을 점화식 이라고 합니다. 점화식으로 수열을 정하려면 두 가지가 필요합니다.
초기항. 어디서 시작하는지 정해야 합니다.관계식. 앞 항에서 다음 항을 어떻게 만드는지 정해야 합니다.
둘 중 하나라도 빠지면 수열이 하나로 정해지지 않습니다. 같은 관계식 a n + 1 = a n + 4 a n + 1 = a n + 4 a 1 = 3 a 1 = 3 3 , 7 , 11 , … 3 , 7 , 1 1 , … a 1 = 0 a 1 = 0 0 , 4 , 8 , … 0 , 4 , 8 , …
지표만 넣으면 값이 나오는 식을 닫힌 형태 라고 합니다. 두 형태의 차이를 정리합니다.
점화식
닫힌 형태
모양
a n + 1 = a n + 4 a n + 1 = a n + 4 a 1 = 3 a 1 = 3 a n = 4 n − 1 a n = 4 n − 1
a n a n n − 1 n − 1 한 번 계산합니다
만들기
쉽습니다
어렵습니다
n n 보이지 않습니다
바로 보입니다
마지막 줄이 33강에서 결정적입니다. a n = 4 n − 1 a n = 4 n − 1 n n
25강에서 확인한 대로 닫힌 형태를 찾는 일과 검증하는 일은 다릅니다. 이 강의는 찾는 쪽이고, 찾은 뒤에는 귀납법으로 검증하는 것이 안전합니다.
바로 확인.
확인 1-1. a 1 = 2 a 1 = 2 a n + 1 = 3 a n a n + 1 = 3 a n
답. 3 3 n − 1 n − 1 a n = 2 ⋅ 3 n − 1 a n = 2 ⋅ 3 n − 1
확인 1-2. a n = 5 n + 2 a n = 5 n + 2
답. a n + 1 − a n = 5 a n + 1 − a n = 5 a n + 1 = a n + 5 a n + 1 = a n + 5 a 1 = 7 a 1 = 7
확인 1-3. 관계식만 주고 초기항을 주지 않으면 무엇이 문제입니까?
답. 수열이 하나로 정해지지 않습니다. 초기항마다 서로 다른 수열이 나옵니다.
문제. a 1 = 1 a 1 = 1 a n + 1 = 2 a n + 3 a n + 1 = 2 a n + 3
생각의 실마리. + 3 + 3 + 3 + 3 b n = a n + c b n = a n + c c c b b c c
풀이. b n = a n + c b n = a n + c b b c c a n = b n − c a n = b n − c
b n + 1 − c = 2 ( b n − c ) + 3 b n + 1 − c = 2 ( b n − c ) + 3
b n + 1 = 2 b n − 2 c + c + 3 = 2 b n + ( 3 − c ) b n + 1 = 2 b n − 2 c + c + 3 = 2 b n + ( 3 − c )
상수항 3 − c 3 − c c = 3 c = 3
b n = a n + 3 , b n + 1 = 2 b n b n = a n + 3 , b n + 1 = 2 b n
이고 b b 2 2 b 1 = a 1 + 3 = 4 b 1 = a 1 + 3 = 4
b n = 4 ⋅ 2 n − 1 = 2 n + 1 b n = 4 ⋅ 2 n − 1 = 2 n + 1
되돌리면
a n = b n − 3 = 2 n + 1 − 3 a n = b n − 3 = 2 n + 1 − 3
입니다. 검산합니다. a 1 = 4 − 3 = 1 a 1 = 4 − 3 = 1 a 2 = 8 − 3 = 5 a 2 = 8 − 3 = 5 2 ⋅ 1 + 3 = 5 2 ⋅ 1 + 3 = 5
이 문제에서 배우는 것: 고정점 이동.
a n + 1 = p a n + q ( p ≠ 1 ) a n + 1 = p a n + q ( p = 1 )
꼴을 푸는 표준 절차는 다음과 같습니다.
고정점을 구합니다. x = p x + q x = p x + q x = q 1 − p x = 1 − p q b n = a n − x b n = a n − x b n + 1 = p b n b n + 1 = p b n 등비수열을 풀어 b n = b 1 p n − 1 b n = b 1 p n − 1
되돌려 a n = x + ( a 1 − x ) p n − 1 a n = x + ( a 1 − x ) p n − 1
a n = q 1 − p + ( a 1 − q 1 − p ) p n − 1 a n = 1 − p q + ( a 1 − 1 − p q ) p n − 1
1번의 x x 고정점 이라고 합니다. a n = x a n = x a n + 1 = x a n + 1 = x x = 3 1 − 2 = − 3 x = 1 − 2 3 = − 3 b n = a n − ( − 3 ) = a n + 3 b n = a n − ( − 3 ) = a n + 3
이 방법이 통하는 이유를 그림으로 말하면 이렇습니다. 고정점을 원점으로 옮기면 남는 것은 순수한 배율 p p q q
p = 1 p = 1 x = x + q x = x + q q ≠ 0 q = 0
∣ p ∣ < 1 ∣ p ∣ < 1 p n − 1 p n − 1 0 0 a n a n
바로 확인.
확인 2-1. a 1 = 2 a 1 = 2 a n + 1 = 3 a n − 4 a n + 1 = 3 a n − 4
답. 고정점은 x = 3 x − 4 x = 3 x − 4 x = 2 x = 2 b n = a n − 2 b n = a n − 2 b 1 = 0 b 1 = 0 n n b n = 0 b n = 0 a n = 2 a n = 2
확인 2-2. a 1 = 5 a 1 = 5 a n + 1 = 1 2 a n + 1 a n + 1 = 2 1 a n + 1
답. 고정점은 x = 1 2 x + 1 x = 2 1 x + 1 x = 2 x = 2 b n = a n − 2 b n = a n − 2 b 1 = 3 b 1 = 3 b n = 3 ( 1 2 ) n − 1 b n = 3 ( 2 1 ) n − 1 a n = 2 + 3 ( 1 2 ) n − 1 a n = 2 + 3 ( 2 1 ) n − 1
확인 2-3. 확인 2-2에서 n n a n a n
답. ( 1 2 ) n − 1 ( 2 1 ) n − 1 2 2
문제. a 1 = 1 a 1 = 1 a n + 1 = a n + 2 n a n + 1 = a n + 2 n
생각의 실마리. 더해지는 양이 상수가 아니라 n n a 1 a 1 a n a n
풀이. 점화식을 차분 꼴로 적습니다.
a k + 1 − a k = 2 k a k + 1 − a k = 2 k
k = 1 k = 1 k = n − 1 k = n − 1
∑ k = 1 n − 1 ( a k + 1 − a k ) = a n − a 1 k = 1 ∑ n − 1 ( a k + 1 − a k ) = a n − a 1
입니다. 오른쪽은
∑ k = 1 n − 1 2 k = 2 ⋅ ( n − 1 ) n 2 = n ( n − 1 ) k = 1 ∑ n − 1 2 k = 2 ⋅ 2 ( n − 1 ) n = n ( n − 1 )
입니다. 따라서
a n − 1 = n ( n − 1 ) , a n = n 2 − n + 1 a n − 1 = n ( n − 1 ) , a n = n 2 − n + 1
검산합니다. a 1 = 1 a 1 = 1 a 2 = 4 − 2 + 1 = 3 a 2 = 4 − 2 + 1 = 3 1 + 2 = 3 1 + 2 = 3 a 3 = 9 − 3 + 1 = 7 a 3 = 9 − 3 + 1 = 7 3 + 4 = 7 3 + 4 = 7
이 문제에서 배우는 것: 계차형 점화식.
a n + 1 = a n + f ( n ) a n + 1 = a n + f ( n )
꼴을 계차형 이라고 합니다. 차분이 f ( n ) f ( n )
a n = a 1 + ∑ k = 1 n − 1 f ( k ) ( n ≥ 2 ) a n = a 1 + k = 1 ∑ n − 1 f ( k ) ( n ≥ 2 )
여기서 위끝이 n − 1 n − 1 n n 이 가장 흔한 실수 자리입니다. a 1 a 1 a n a n n − 1 n − 1 n = 2 n = 2 a 2 = a 1 + f ( 1 ) a 2 = a 1 + f ( 1 )
이 방법이 통하려면 ∑ f ( k ) ∑ f ( k )
f ( n ) f ( n ) 필요한 합 공식
상수 d d
∑ d = d ( n − 1 ) ∑ d = d ( n − 1 )
n n ∑ k ∑ k ∑ k 2 ∑ k 2
r^
등비수열의 합
\dfrac{1}
망원합
곱셈 꼴인 a n + 1 = g ( n ) a n a n + 1 = g ( n ) a n
a n = a 1 ∏ k = 1 n − 1 g ( k ) a n = a 1 k = 1 ∏ n − 1 g ( k )
바로 확인.
확인 3-1. a 1 = 0 a 1 = 0 a n + 1 = a n + n a n + 1 = a n + n
답. a n = 0 + ∑ k = 1 n − 1 k = ( n − 1 ) n 2 a n = 0 + k = 1 ∑ n − 1 k = 2 ( n − 1 ) n
확인 3-2. a 1 = 1 a 1 = 1 a n + 1 = a n + 3 n a n + 1 = a n + 3 n
답. a n = 1 + ∑ k = 1 n − 1 3 k = 1 + 3 n − 3 2 = 3 n − 1 2 a n = 1 + k = 1 ∑ n − 1 3 k = 1 + 2 3 n − 3 = 2 3 n − 1
확인 3-3. a 1 = 1 a 1 = 1 a n + 1 = n n + 1 a n a n + 1 = n + 1 n a n
답. a n = ∏ k = 1 n − 1 k k + 1 a n = k = 1 ∏ n − 1 k + 1 k a n = 1 n a n = n 1
문제. 피보나치 수열은 F 1 = 1 F 1 = 1 F 2 = 1 F 2 = 1 F n + 2 = F n + 1 + F n F n + 2 = F n + 1 + F n
생각의 실마리. 앞의 두 항이 필요하므로 지금까지의 방법이 통하지 않습니다. 대신 답의 모양을 먼저 추측해 봅니다. 문제 2에서 답이 p n p n a n = t n a n = t n t t
풀이. a n = t n a n = t n
t n + 2 = t n + 1 + t n t n + 2 = t n + 1 + t n
t ≠ 0 t = 0 t n t n
t 2 = t + 1 , t 2 − t − 1 = 0 t 2 = t + 1 , t 2 − t − 1 = 0
5강의 근의 공식으로 풉니다.
t = 1 ± 5 2 t = 2 1 ± 5
두 근을 α = 1 + 5 2 α = 2 1 + 5 β = 1 − 5 2 β = 2 1 − 5
α n α n β n β n A α n + B β n A α n + B β n
A α n + 2 + B β n + 2 = A ( α n + 1 + α n ) + B ( β n + 1 + β n ) A α n + 2 + B β n + 2 = A ( α n + 1 + α n ) + B ( β n + 1 + β n )
이 성립합니다. 이제 초기 조건으로 A A B B
A α + B β = 1 , A α 2 + B β 2 = 1 A α + B β = 1 , A α 2 + B β 2 = 1
7강의 연립방정식을 풉니다. α 2 = α + 1 α 2 = α + 1 β 2 = β + 1 β 2 = β + 1
A ( α + 1 ) + B ( β + 1 ) = 1 A ( α + 1 ) + B ( β + 1 ) = 1
이고, 첫 식 A α + B β = 1 A α + B β = 1 A + B = 0 A + B = 0 B = − A B = − A
A ( α − β ) = 1 , α − β = 5 A ( α − β ) = 1 , α − β = 5
이므로 A = 1 5 A = 5 1 B = − 1 5 B = − 5 1
F n = 1 5 [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ] F n = 5 1 [ ( 2 1 + 5 ) n − ( 2 1 − 5 ) n ]
입니다. 검산합니다. n = 1 n = 1 1 5 ⋅ 5 = 1 5 1 ⋅ 5 = 1 n = 2 n = 2 α 2 − β 2 = ( α + β ) ( α − β ) = 1 ⋅ 5 α 2 − β 2 = ( α + β ) ( α − β ) = 1 ⋅ 5 1 1
이 문제에서 배우는 것: 특성방정식.
a n + 2 = p a n + 1 + q a n a n + 2 = p a n + 1 + q a n
꼴을 이차 선형 점화식 이라고 합니다. 푸는 절차는 다음과 같습니다.
a n = t n a n = t n 특성방정식 t 2 = p t + q t 2 = p t + q 두 근 α , β α , β
a n = A α n + B β n a n = A α n + B β n 초기항 두 개를 대입해 A A B B
3번이 정당한 이유는 점화식이 선형 이기 때문입니다. 해 두 개를 상수배해 더해도 여전히 해가 되며, 이 성질을 중첩이라고 합니다. 62강 이후 선형대수학에서 같은 성질이 이론의 중심이 됩니다.
초기항이 두 개 필요하다는 점도 확인해 둡니다. 미지수 A A B B
얻은 식은 비네 공식 이라고 하며 놀라운 점이 있습니다. 5 5 β = 1 − 5 2 ≈ − 0.618 β = 2 1 − 5 ≈ − 0 . 6 1 8 ∣ β ∣ < 1 ∣ β ∣ < 1 β n β n n n
F n ≈ α n 5 F n ≈ 5 α n
가 됩니다. 여기서 α ≈ 1.618 α ≈ 1 . 6 1 8 1.618 1 . 6 1 8 n n
바로 확인.
확인 4-1. a 1 = 1 a 1 = 1 a 2 = 5 a 2 = 5 a n + 2 = 5 a n + 1 − 6 a n a n + 2 = 5 a n + 1 − 6 a n
답. 특성방정식 t 2 − 5 t + 6 = 0 t 2 − 5 t + 6 = 0 2 2 3 3 a n = A ⋅ 2 n + B ⋅ 3 n a n = A ⋅ 2 n + B ⋅ 3 n 2 A + 3 B = 1 2 A + 3 B = 1 4 A + 9 B = 5 4 A + 9 B = 5 A = − 1 A = − 1 B = 1 B = 1 a n = 3 n − 2 n a n = 3 n − 2 n
확인 4-2. 특성방정식은 어떻게 얻습니까?
답. a n = t n a n = t n t n t n
확인 4-3. 이차 선형 점화식에 초기항이 두 개 필요한 이유를 쓰세요.
답. 일반해에 미지수 A A B B
문제. (1) a 1 = 1 a 1 = 1 a 2 = 4 a 2 = 4 a n + 2 = 4 a n + 1 − 4 a n a n + 2 = 4 a n + 1 − 4 a n a n = A ⋅ 2 n + B ⋅ 2 n a n = A ⋅ 2 n + B ⋅ 2 n a 1 = 1 a 1 = 1 a 2 = 0 a 2 = 0 a n + 2 = − a n a n + 2 = − a n
생각의 실마리. (1)에서 두 근이 같으면 A α n + B α n = ( A + B ) α n A α n + B α n = ( A + B ) α n
풀이. (1) 특성방정식은 t 2 − 4 t + 4 = ( t − 2 ) 2 = 0 t 2 − 4 t + 4 = ( t − 2 ) 2 = 0 2 2
a n = A ⋅ 2 n + B ⋅ 2 n a n = A ⋅ 2 n + B ⋅ 2 n ( A + B ) 2 n ( A + B ) 2 n C = A + B C = A + B 2 C = 1 2 C = 1 C = 1 2 C = 2 1 4 C = 4 4 C = 4 C = 1 C = 1
해결책은 두 번째 해를 다른 모양에서 찾는 것입니다. 중근일 때는 n α n n α n a n = n ⋅ 2 n a n = n ⋅ 2 n
4 ( n + 1 ) 2 n + 1 − 4 n ⋅ 2 n = 2 n ( 8 n + 8 − 4 n ) = 2 n ( 4 n + 8 ) 4 ( n + 1 ) 2 n + 1 − 4 n ⋅ 2 n = 2 n ( 8 n + 8 − 4 n ) = 2 n ( 4 n + 8 )
이고 좌변의 a n + 2 = ( n + 2 ) 2 n + 2 = 2 n ( 4 n + 8 ) a n + 2 = ( n + 2 ) 2 n + 2 = 2 n ( 4 n + 8 )
따라서 a n = ( A + B n ) 2 n a n = ( A + B n ) 2 n 2 ( A + B ) = 1 2 ( A + B ) = 1 4 ( A + 2 B ) = 4 4 ( A + 2 B ) = 4 A + B = 1 2 A + B = 2 1 A + 2 B = 1 A + 2 B = 1 B = 1 2 B = 2 1 A = 0 A = 0
a n = n 2 ⋅ 2 n = n ⋅ 2 n − 1 a n = 2 n ⋅ 2 n = n ⋅ 2 n − 1
검산하면 a 1 = 1 a 1 = 1 a 2 = 4 a 2 = 4 a 3 = 12 a 3 = 1 2 4 ⋅ 4 − 4 ⋅ 1 = 12 4 ⋅ 4 − 4 ⋅ 1 = 1 2
(2) 특성방정식은 t 2 = − 1 t 2 = − 1 t = ± i t = ± i
a n = A i n + B ( − i ) n a n = A i n + B ( − i ) n
초기 조건을 넣습니다. n = 1 n = 1 A i − B i = 1 A i − B i = 1 n = 2 n = 2 A i 2 + B ( − i ) 2 = − A − B = 0 A i 2 + B ( − i ) 2 = − A − B = 0 B = − A B = − A 2 A i = 1 2 A i = 1 A = 1 2 i = − i 2 A = 2 i 1 = − 2 i B = i 2 B = 2 i
a n = − i 2 i n + i 2 ( − i ) n a n = − 2 i i n + 2 i ( − i ) n
i i 4 4 1 , 0 , − 1 , 0 , 1 , 0 , − 1 , 0 , … 1 , 0 , − 1 , 0 , 1 , 0 , − 1 , 0 , … a n + 2 = − a n a n + 2 = − a n 4 4
이 문제에서 배우는 것: 중근과 허근의 처리.
특성방정식의 근에 따라 일반해의 모양이 달라집니다. 6강의 판별식이 여기서 다시 쓰입니다.
판별식
근
일반해
D > 0 D > 0 서로 다른 실근 α , β α , β
a_{n}=A\alpha^{n}+B\beta^
D = 0 D = 0 중근 α α
a_{n}=(A+Bn)\alpha^
D < 0 D < 0 켤레 허근
a_{n}=A\alpha^{n}+B\bar{\alpha}^
중근일 때 n α n n α n 초기 조건이 두 개이므로 서로 다른 해가 두 개 필요합니다.
허근일 때는 30강의 극형식을 쓰면 결과를 실수로 읽을 수 있습니다. α = r ( cos θ + i sin θ ) α = r ( cos θ + i sin θ )
a n = r n ( C cos n θ + D sin n θ ) a n = r n ( C cos n θ + D sin n θ )
꼴로 정리됩니다. 여기서 C C D D ∣ ± i ∣ = 1 ∣ ± i ∣ = 1 ± π 2 ± 2 π a n a n cos n π 2 cos 2 n π sin n π 2 sin 2 n π 4 4
허근은 진동을 뜻합니다. 실근이면 수열이 지수적으로 커지거나 줄어들고, 허근이면 삼각함수가 나타나 값이 오르내립니다. 이 대응은 뒤에서 계속 나타납니다. 58강의 오일러 공식이 지수와 삼각함수를 잇는 다리이며, 그 다리의 첫 흔적이 여기 있습니다.
마지막으로 검증을 잊지 않습니다. 이 강의의 방법으로 얻은 닫힌 형태는 모두 추측을 세우고 초기 조건으로 맞춘 것 이므로, 25강의 귀납법으로 확인하면 확실합니다. 실전에서는 작은 n n
바로 확인.
확인 5-1. a n + 2 = 6 a n + 1 − 9 a n a n + 2 = 6 a n + 1 − 9 a n
답. t 2 − 6 t + 9 = ( t − 3 ) 2 = 0 t 2 − 6 t + 9 = ( t − 3 ) 2 = 0 3 3 a n = ( A + B n ) 3 n a n = ( A + B n ) 3 n
확인 5-2. a n + 2 = 2 a n + 1 − 2 a n a n + 2 = 2 a n + 1 − 2 a n
답. t 2 − 2 t + 2 = 0 t 2 − 2 t + 2 = 0 t = 2 ± − 4 2 = 1 ± i t = 2 2 ± − 4 = 1 ± i
확인 5-3. 확인 5-2의 근의 절댓값과 편각을 구하고 수열의 거동을 말하세요.
답. ∣ 1 + i ∣ = 2 ∣ 1 + i ∣ = 2 π 4 4 π a n = ( 2 ) n ( C cos n π 4 + D sin n π 4 ) a n = ( 2 ) n ( C cos 4 n π + D sin 4 n π ) ( 2 ) n ( 2 ) n
점화식
푸는 법
닫힌 형태
a n + 1 = a n + d a n + 1 = a n + d 등차
a n = a 1 + ( n − 1 ) d a n = a 1 + ( n − 1 ) d
a_{n+1}=ra_
등비
a_{n}=a_{1}r^
a n + 1 = p a n + q a n + 1 = p a n + q 고정점 이동
a n = x + ( a 1 − x ) p n − 1 a n = x + ( a 1 − x ) p n − 1
a n + 1 = a n + f ( n ) a n + 1 = a n + f ( n ) 계차, 합으로
a n = a 1 + ∑ k = 1 n − 1 f ( k ) a n = a 1 + ∑ k = 1 n − 1 f ( k )
a_{n+1}=g(n)a_
곱으로
a n = a 1 ∏ k = 1 n − 1 g ( k ) a n = a 1 ∏ k = 1 n − 1 g ( k )
a_{n+2}=pa_{n+1}+qa_
특성방정식
근에 따라 아래 표
특성근
일반해
서로 다른 실근
A\alpha^{n}+B\beta^
중근
(A+Bn)\alpha^
켤레 허근
r n ( C cos n θ + D sin n θ ) r n ( C cos n θ + D sin n θ )
자주 하는 실수
확인 방법
합의 위끝을 n n
n = 2 n = 2 a 2 = a 1 + f ( 1 ) a 2 = a 1 + f ( 1 )
중근인데 A α n + B α n A α n + B α n
미지수가 하나로 줄어드는지 봅니다
초기항을 쓰지 않음
미지수 개수와 조건 개수를 맞춥니다
검증 생략
작은 n n
문제 6. a 1 = 4 a 1 = 4 a n + 1 = a n − 3 a n + 1 = a n − 3
답. a n = 4 − 3 ( n − 1 ) = 7 − 3 n a n = 4 − 3 ( n − 1 ) = 7 − 3 n
문제 7. a 1 = 3 a 1 = 3 a n + 1 = 2 a n a n + 1 = 2 a n
답. a n = 3 ⋅ 2 n − 1 a n = 3 ⋅ 2 n − 1
문제 8. a 1 = 1 a 1 = 1 a n + 1 = 3 a n + 2 a n + 1 = 3 a n + 2
답. 고정점은 x = 3 x + 2 x = 3 x + 2 x = − 1 x = − 1 b n = a n + 1 b n = a n + 1 b 1 = 2 b 1 = 2 b n = 2 ⋅ 3 n − 1 b n = 2 ⋅ 3 n − 1 a n = 2 ⋅ 3 n − 1 − 1 a n = 2 ⋅ 3 n − 1 − 1
문제 9. a 1 = 2 a 1 = 2 a n + 1 = 1 3 a n + 4 a n + 1 = 3 1 a n + 4 n n
답. x = 1 3 x + 4 x = 3 1 x + 4 x = 6 x = 6 ( 1 3 ) n − 1 ( 3 1 ) n − 1 a n a n 6 6
문제 10. a 1 = 1 a 1 = 1 a n + 1 = a n + n 2 a n + 1 = a n + n 2
답. a n = 1 + ∑ k = 1 n − 1 k 2 = 1 + ( n − 1 ) n ( 2 n − 1 ) 6 a n = 1 + k = 1 ∑ n − 1 k 2 = 1 + 6 ( n − 1 ) n ( 2 n − 1 )
문제 11. a 1 = 1 a 1 = 1 a n + 1 = a n 2 a n + 1 = 2 a n a 10 a 1 0
답. a n = ( 1 2 ) n − 1 a n = ( 2 1 ) n − 1 a 10 = 1 512 a 1 0 = 5 1 2 1
문제 12. a 1 = 1 a 1 = 1 a 2 = 2 a 2 = 2 a n + 2 = 3 a n + 1 − 2 a n a n + 2 = 3 a n + 1 − 2 a n
답. t 2 − 3 t + 2 = 0 t 2 − 3 t + 2 = 0 1 1 2 2 A + 2 B = 1 A + 2 B = 1 A + 4 B = 2 A + 4 B = 2 B = 1 2 B = 2 1 A = 0 A = 0 a n = 2 n − 1 a n = 2 n − 1
문제 13. 피보나치 수열에서 F 10 F 1 0
답. 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 1 , 1 , 2 , 3 , 5 , 8 , 1 3 , 2 1 , 3 4 , 5 5 F 10 = 55 F 1 0 = 5 5
문제 14. 비네 공식에서 n n F n + 1 F n F n F n + 1
답. β n β n α = 1 + 5 2 α = 2 1 + 5
문제 15. a n + 2 = a n + 1 + 6 a n a n + 2 = a n + 1 + 6 a n
답. t 2 − t − 6 = ( t − 3 ) ( t + 2 ) = 0 t 2 − t − 6 = ( t − 3 ) ( t + 2 ) = 0 3 3 − 2 − 2 a n = A ⋅ 3 n + B ( − 2 ) n a n = A ⋅ 3 n + B ( − 2 ) n
문제 16. a 1 = 1 a 1 = 1 a n + 1 = a n + 1 n ( n + 1 ) a n + 1 = a n + n ( n + 1 ) 1
답. 망원합이므로 a n = 1 + ( 1 − 1 n ) = 2 − 1 n a n = 1 + ( 1 − n 1 ) = 2 − n 1
문제 17. 하노이 탑에서 원반 n n h 1 = 1 h 1 = 1 h n + 1 = 2 h n + 1 h n + 1 = 2 h n + 1
답. 고정점은 x = 2 x + 1 x = 2 x + 1 x = − 1 x = − 1 b n = h n + 1 b n = h n + 1 b 1 = 2 b 1 = 2 b n = 2 n b n = 2 n h n = 2 n − 1 h n = 2 n − 1
문제 18. 25강 심화 5에서 n n A k + 1 = A k + ( k + 1 ) A k + 1 = A k + ( k + 1 ) A 0 = 1 A 0 = 1
답. A n = 1 + ∑ k = 0 n − 1 ( k + 1 ) = 1 + ∑ j = 1 n j = 1 + n ( n + 1 ) 2 = n 2 + n + 2 2 A n = 1 + k = 0 ∑ n − 1 ( k + 1 ) = 1 + j = 1 ∑ n j = 1 + 2 n ( n + 1 ) = 2 n 2 + n + 2
심화 1. 문제 4에서 얻은 비네 공식이 항상 정수를 준다는 사실을 설명하세요.
답. 5 5
풀이. 20강의 이항정리로 α n α n β n β n α = 1 + 5 2 α = 2 1 + 5 β = 1 − 5 2 β = 2 1 − 5 5 5 α n − β n α n − β n 5 5 5 5 5 5 1 5 5 1
남는 것. 무리수를 거쳐 정수에 도달하는 계산입니다. 24강에서 무리수를 다룬 것과 20강에서 이항정리를 세운 것이 여기서 만납니다. 이 구조는 30강 문제 15에서 실수 계수 방정식의 허근이 켤레쌍으로 나타나 서로 상쇄되던 것과 같습니다. 켤레끼리 짝지어 무리수 부분이 지워지는 것 이 공통 원리입니다.
심화 2. 중근일 때 n α n n α n
답. 중근이면 특성다항식과 그 도함수가 같은 근을 가지기 때문입니다.
풀이. 특성다항식을 P ( t ) = t 2 − p t − q P ( t ) = t 2 − p t − q α α P ( t ) = ( t − α ) 2 P ( t ) = ( t − α ) 2 a n = n α n a n = n α n
( n + 2 ) α n + 2 − p ( n + 1 ) α n + 1 − q n α n = α n [ n ( α 2 − p α − q ) + ( 2 α 2 − p α ) ] ( n + 2 ) α n + 2 − p ( n + 1 ) α n + 1 − q n α n = α n [ n ( α 2 − p α − q ) + ( 2 α 2 − p α ) ]
가 됩니다. 첫 괄호는 P ( α ) = 0 P ( α ) = 0 α ( 2 α − p ) α ( 2 α − p ) 2 α = p 2 α = p 0 0 0 0
남는 것. 둘째 괄호가 α P ′ ( α ) α P ′ ( α ) P ′ ( t ) = 2 t − p P ′ ( t ) = 2 t − p P ( α ) = P ′ ( α ) = 0 P ( α ) = P ′ ( α ) = 0
심화 3. a n + 1 = 2 a n + 3 a n + 4 a n + 1 = a n + 4 2 a n + 3
답. 고정점은 1 1 − 3 − 3
풀이. x = 2 x + 3 x + 4 x = x + 4 2 x + 3 x ( x + 4 ) = 2 x + 3 x ( x + 4 ) = 2 x + 3 x 2 + 2 x − 3 = 0 x 2 + 2 x − 3 = 0 ( x + 3 ) ( x − 1 ) = 0 ( x + 3 ) ( x − 1 ) = 0 x = 1 x = 1 x = − 3 x = − 3
a 1 = 1 a 1 = 1 a 2 = 2 + 3 1 + 4 = 1 a 2 = 1 + 4 2 + 3 = 1 1 1 a 1 = − 3 a 1 = − 3 a 2 = − 6 + 3 − 3 + 4 = − 3 a 2 = − 3 + 4 − 6 + 3 = − 3
남는 것. 고정점은 문제 2의 일차 꼴에만 있는 개념이 아니라 a n + 1 = g ( a n ) a n + 1 = g ( a n ) x = g ( x ) x = g ( x )
심화 4. a n + 1 = p a n + f ( n ) a n + 1 = p a n + f ( n ) n n a 1 = 1 a 1 = 1 a n + 1 = 2 a n + n a n + 1 = 2 a n + n
답. 양변을 p n + 1 p n + 1 a n = 3 ⋅ 2 n − 1 − n − 1 a n = 3 ⋅ 2 n − 1 − n − 1
풀이. 점화식의 양변을 2 n + 1 2 n + 1
a n + 1 2 n + 1 = a n 2 n + n 2 n + 1 2 n + 1 a n + 1 = 2 n a n + 2 n + 1 n
b n = a n 2 n b n = 2 n a n b n + 1 = b n + n 2 n + 1 b n + 1 = b n + 2 n + 1 n
b n = b 1 + ∑ k = 1 n − 1 k 2 k + 1 b n = b 1 + k = 1 ∑ n − 1 2 k + 1 k
입니다. b 1 = 1 2 b 1 = 2 1 ∑ k = 1 m k 2 k = 2 − m + 2 2 m ∑ k = 1 m 2 k k = 2 − 2 m m + 2 m = n − 1 m = n − 1 1 2 2 1
∑ k = 1 n − 1 k 2 k + 1 = 1 − n + 1 2 n k = 1 ∑ n − 1 2 k + 1 k = 1 − 2 n n + 1
이므로 b n = 3 2 − n + 1 2 n b n = 2 3 − 2 n n + 1 2 n 2 n a n = 3 ⋅ 2 n − 1 − n − 1 a n = 3 ⋅ 2 n − 1 − n − 1
검산합니다. a 1 = 3 − 2 = 1 a 1 = 3 − 2 = 1 a 2 = 6 − 3 = 3 a 2 = 6 − 3 = 3 2 ⋅ 1 + 1 = 3 2 ⋅ 1 + 1 = 3 a 3 = 12 − 4 = 8 a 3 = 1 2 − 4 = 8 2 ⋅ 3 + 2 = 8 2 ⋅ 3 + 2 = 8
남는 것. 적분인자를 곱해 계차형으로 만드는 이 수법은 미분방정식에서 그대로 재사용됩니다. y ′ = p y + f ( x ) y ′ = p y + f ( x ) e − p x e − p x
심화 5. 문제 4의 방법으로 얻은 비네 공식을 25강의 강한 귀납법으로 검증하세요.
답. 기초 단계 두 개와 귀납 단계로 증명됩니다.
풀이. G n = α n − β n 5 G n = 5 α n − β n G n = F n G n = F n
기초 단계에서 G 1 = α − β 5 = 1 G 1 = 5 α − β = 1 G 2 = ( α + β ) ( α − β ) 5 = 1 G 2 = 5 ( α + β ) ( α − β ) = 1 α + β = 1 α + β = 1 F 1 = F 2 = 1 F 1 = F 2 = 1
귀납 단계에서 G k = F k G k = F k G k + 1 = F k + 1 G k + 1 = F k + 1 α 2 = α + 1 α 2 = α + 1 α k + 2 = α k + 1 + α k α k + 2 = α k + 1 + α k β β
G k + 2 = α k + 2 − β k + 2 5 = ( α k + 1 − β k + 1 ) + ( α k − β k ) 5 = G k + 1 + G k G k + 2 = 5 α k + 2 − β k + 2 = 5 ( α k + 1 − β k + 1 ) + ( α k − β k ) = G k + 1 + G k
이고 귀납 가정에 의해 이는 F k + 1 + F k = F k + 2 F k + 1 + F k = F k + 2
남는 것. 25강 확인 4-1에서 피보나치에는 강한 귀납법과 기초 단계 두 개가 필요하다고 했는데, 그 이유가 여기서 실제로 드러납니다. 귀납 단계에서 G k G k G k + 1 G k + 1 둘 다 썼습니다. 그리고 이 검증이 이 강의의 방법 전체를 정당화합니다. 추측으로 얻은 식을 귀납법이 확정해 줍니다.
심화 6. 이차 선형 점화식의 해가 초기항 두 개로 유일하게 정해짐을 증명하세요.
답. 25강의 강한 귀납법으로 증명됩니다.
풀이. 같은 점화식과 같은 초기항 a 1 , a 2 a 1 , a 2 x n x n y n y n P ( n ) P ( n ) x n = y n x n = y n
기초 단계에서 x 1 = a 1 = y 1 x 1 = a 1 = y 1 x 2 = a 2 = y 2 x 2 = a 2 = y 2
귀납 단계에서 x k = y k x k = y k x k + 1 = y k + 1 x k + 1 = y k + 1
x k + 2 = p x k + 1 + q x k = p y k + 1 + q y k = y k + 2 x k + 2 = p x k + 1 + q x k = p y k + 1 + q y k = y k + 2
입니다. 따라서 모든 n n
남는 것. 이 결과가 이 강의의 절차를 정당화합니다. 우리는 해의 모양을 추측 해서 A α n + B β n A α n + B β n 추측을 정당화하는 도구 로 쓰였습니다.
점화식으로 직접 계산한 값과 손으로 구한 닫힌 형태를 대조하는 것이 가장 확실한 검산입니다. 두 배열이 완전히 일치하면 닫힌 형태가 맞습니다.
import numpy as np
N = 20
n = np.arange(1, N + 1)
def recur1(a1, step, N):
out = [a1]
for k in range(1, N):
out.append(step(out[-1], k))
return np.array(out, dtype=float)
# 문제 2: a_{n+1} = 2a_n + 3, a_1 = 1 -> a_n = 2^(n+1) - 3
seq = recur1(1.0, lambda a, k: 2*a + 3, N)
print(np.allclose(seq, 2.0**(n + 1) - 3)) # True
# 문제 3: a_{n+1} = a_n + 2n, a_1 = 1 -> a_n = n^2 - n + 1
seq = recur1(1.0, lambda a, k: a + 2*k, N)
print(np.allclose(seq, n**2 - n + 1)) # True
# 문제 17: 하노이 탑 h_n = 2^n - 1
seq = recur1(1.0, lambda a, k: 2*a + 1, N)
print(np.allclose(seq, 2.0**n - 1)) # True
# 문제 4: 피보나치와 비네 공식
F = [1.0, 1.0]
for _ in range(N - 2):
F.append(F[-1] + F[-2])
F = np.array(F)
al, be = (1 + np.sqrt(5)) / 2, (1 - np.sqrt(5)) / 2
binet = (al**n - be**n) / np.sqrt(5)
print(np.allclose(F, binet)) # True
print([int(round(v)) for v in F[:10]])
# [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
print(round(float(F[-1] / F[-2]), 8), round(float(al), 8))
# 1.61803396 1.61803399
# 문제 5 (1): 중근이면 (A + Bn) alpha^n 이 필요합니다.
seq = [1.0, 4.0]
for _ in range(N - 2):
seq.append(4*seq[-1] - 4*seq[-2])
seq = np.array(seq)
print(np.allclose(seq, n * 2.0**(n - 1))) # True
# 문제 5 (2): 허근이면 진동합니다.
seq = [1.0, 0.0]
for _ in range(10):
seq.append(-seq[-2])
print([int(v) for v in seq])
# [1, 0, -1, 0, 1, 0, -1, 0, 1, 0, -1, 0]
# 심화 4: a_{n+1} = 2a_n + n -> a_n = 3*2^(n-1) - n - 1
seq = recur1(1.0, lambda a, k: 2*a + k, N)
print(np.allclose(seq, 3 * 2.0**(n - 1) - n - 1)) # True
# 확인 5-3: 허근의 절댓값이 1보다 크면 진폭이 커집니다.
seq = [1.0, 1.0]
for _ in range(8):
seq.append(2*seq[-1] - 2*seq[-2])
print([int(v) for v in seq])
# [1, 1, 0, -2, -4, -4, 0, 8, 16, 16]
출력이 주석과 모두 일치합니다. 네 번째 검산에서 F 20 / F 19 = 1.61803396 F 2 0 / F 1 9 = 1 . 6 1 8 0 3 3 9 6 α = 1.61803399 α = 1 . 6 1 8 0 3 3 9 9 α α n n α α β n β n ( 2 ) n ( 2 ) n
점화식으로 수열을 정하려면 무엇이 필요합니까?
닫힌 형태의 장점 두 가지를 쓰세요.
a n + 1 = p a n + q a n + 1 = p a n + q 계차형에서 합의 위끝은 무엇입니까?
특성방정식은 어떻게 얻습니까?
특성방정식이 중근이면 일반해는 어떤 모양입니까?
특성근이 허근이면 수열은 어떤 거동을 보입니까?
찾은 닫힌 형태를 어떻게 검증합니까?
정답.
초기항과 관계식이 필요합니다.
한 번의 계산으로 값을 얻고, n n
x = q 1 − p x = 1 − p q n − 1 n − 1 a n = t n a n = t n t n t n ( A + B n ) α n ( A + B n ) α n 진동합니다. 절댓값에 따라 진폭이 커지거나 줄어듭니다.
작은 n n
기호
읽는 법
뜻
a n + 1 = f ( a n ) a n + 1 = f ( a n ) 점화식
앞 항으로 다음 항을 정합니다
닫힌 형태
closed form
n n
고정점
fixed point
x = f ( x ) x = f ( x )
특성방정식
characteristic equation
t 2 = p t + q t 2 = p t + q
F_
피보나치 수
F 1 = F 2 = 1 F 1 = F 2 = 1 F n + 2 = F n + 1 + F n F n + 2 = F n + 1 + F n
\alpha=\dfrac{1+\sqrt5}
황금비
약 1.618 1 . 6 1 8
이 강의로 03단원과 S2 수학의 언어가 모두 끝납니다. 21강부터 25강까지 논리와 증명을 세우고, 26강부터 29강까지 집합과 함수를 정의하고, 30강부터 32강까지 복소수와 합 기호와 점화식을 다뤘습니다. 이제 32강 뒤의 관문 1에서 1강부터 32강까지를 섞어 다시 묻습니다. 통과하면 33강부터 미적분학이 시작되며, 그 첫 주제인 수열의 극한이 이 강의에서 만든 닫힌 형태를 곧바로 씁니다.