상자에 물건이 두 개 있다. 한 차례마다 지금 개수의 두 배에 세 개를 더한 새 개수를 기록한다. 다음 기록을 차례로 만드는 방법과, 원하는 차례의 값을 바로 찾는 방법은 같은 기록을 다르게 읽는다.
앞 기록으로 다음 기록을 정한 것이 점화식이다. 차례만 넣어 값을 구하는 식이 일반항이다. 수열의 귀납적 정의에서 처음 값이 필요한 이유를 배웠다면, 이제 그 규칙을 번호만의 식으로 바꿔 보자. 하노이의 탑 이동 횟수나 매일 절반을 비우고 다시 채우는 수조의 물처럼 같은 규칙이 되풀이되는 양도, 100번째 값을 앞의 값 없이 바로 계산할 수 있게 된다.
일차 점화식의 일반항은 처음 값과 두 항의 관계를 함께 만족한다
이 글의 일차 점화식은 바로 앞 항 an 하나로 다음 항 an+1을 정하되, an이 일차식으로만 들어가는 관계다. 상수 r,b로 곱하고 더하는 an+1=ran+b와, 번호에 따라 바뀌는 양을 더하는 an+1=an+f(n)이 대표적이다. an+1=an2처럼 앞 항을 제곱하는 관계는 다루지 않는다.
일반항은 처음 값과 모든 번호의 점화식을 함께 만족하는, 번호 n만의 식이다. 번호는 이전 글의 1 시작과 달리 0부터 센다. 처음 값을 a0라 쓰며, n은 0 이상의 정수다. 1부터 세는 문제는 뒤의 하노이 예에서 바꾸는 법을 다룬다. 대표 규칙은
a0=2,an+1=2an+3(n≥0).(1)
정의
기호
이름
원어
뜻
n
항의 번호
index
0부터 세는 정수
an,a0
제n항, 처음 값
term, initial value
번호 n의 값과 시작 값
r,b
상수 계수, 상수항
coefficient, constant term
번호에 따라 바뀌지 않는 실수
c
고정점
fixed point
c=rc+b를 만족하는 값
un
옮긴 수열
shifted sequence
an−c
f(n),k
증가량, 합의 번호
increment, summation index
항의 차와 그 차를 더할 때의 번호
차례로 계산하면 a1=2⋅2+3=7, a2=2⋅7+3=17, a3=2⋅17+3=37이다. 이 값들만 보고 추측한 식은 아직 증명이 아니다. 처음 값과 모든 번호에서의 관계를 확인해야 한다.
왜 3을 더해 옮기면 등비수열이 될까?
매번 더해지는 3까지 함께 두 배가 되도록 기준을 옮기기 때문이다. 예를 들어 7과 17의 비는 2가 아니지만, 각각 3을 더한 10과 20의 비는 2다.
an+1+3=2an+6=2(an+3).(2)
un=an+3이라 놓으면 u0=5이고 un+1=2un이다. 따라서 un=5⋅2n, 다시 3을 빼면
an=5⋅2n−3(n≥0).(3)
그림 1은 처음 다섯 값을 옮기기 전후로 비교한다. 아래 수열은 공비가 2이고, 위 수열은 같은 번호의 값에서 3씩 작다. 이것은 유한한 예시이며, 모든 번호에 대한 이유는 식 (2)다.
그림 1a0=2, an+1=2an+3의 처음 다섯 항(위)과 un=an+3의 다섯 항(아래)이다. 아래의 5, 10, 20, 40, 80은 두 배씩 커진다. figures/shift_to_geometric.py
일반적으로 an+1=ran+b에서 r=1이면 c=b/(1−r)가 고정점이다. 고정점은 규칙에 넣어도 바뀌지 않는 값이다. c=rc+b를 원래 관계에서 빼면 an+1−c=r(an−c)가 된다. r=0,1인 경우에는
an=c+(a0−c)rn,c=1−rb(n≥0).(4)
식 (1)에서는 c=3/(1−2)=−3이므로 식 (4)가 식 (3)과 같다. r=1이면 나눌 수 없으므로 an=a0+nb를 쓴다. r=0이면 첫 값은 따로 두고 n≥1에서 an=b다. 이처럼 나누어 적으면 00을 사용할 필요도 없다. a0=c라면 바뀌지 않는 상수 수열이라는 점도 식 (4)에 들어 있다.
일차 점화식의 값이 고정점에 가까워질지는 무엇이 정할까?
a0=c일 때는 곱하는 계수 r의 절댓값이 정한다. 식 (4)에서 an−c=(a0−c)rn, 곧 옮긴 수열의 공비가 r이므로, 고정점까지의 거리는 규칙을 한 번 적용할 때마다 ∣r∣배가 된다.
∣an+1−c∣=∣r∣∣an−c∣.(5)
식 (1)은 r=2라서 고정점 −3과의 거리가 5, 10, 20으로 두 배씩 멀어진다. 그림 1 아래 수열의 값이 바로 이 거리다.
∣r∣<1이면 거리가 줄어든다. 빈 수조에서 매일 물의 절반을 빼낸 뒤 2 L를 붓는다고 하자. n일째 물의 양을 an L라 하면 a0=0, an+1=21an+2다. 고정점은 c=2/(1−21)=4이므로 an=4−4(21)n이다.
물의 양은 0, 2, 3, 3.5, 3.75이고, 4와의 거리는 4, 2, 1, 0.5, 0.25로 반씩 준다. 4(21)n은 언제나 양수이므로 물이 정확히 4 L가 되는 날은 없다. r<0이면 고정점의 양쪽을 번갈아 간다. a0=0, an+1=−21an+6도 고정점은 4지만, 값은 0, 6, 3, 4.5, 3.75로 4보다 큰 쪽과 작은 쪽을 오간다.
그림 2는 두 규칙을 가로축 an, 세로축 an+1인 평면에 그렸다. 고정점은 직선 y=rx+b와 y=x의 교점이다. 꺾은선은 직선에서 다음 값을 읽고, y=x에서 그 값을 다시 가로축의 입력으로 옮기는 과정을 되풀이한다.
그림 2a0=0에서 r=1/2,b=2(위)와 r=−1/2,b=6(아래)의 규칙을 네 번 적용한 거미줄 그림이다. 두 직선의 교점이 고정점 c=4이고, 위는 한쪽에서 계단처럼, 아래는 양쪽을 번갈아 가며 4와의 거리가 반씩 준다. figures/fixed_point_cobweb.py
교과서의 특성방정식 풀이는 고정점 풀이와 같은 식을 준다
교과서는 번호를 1부터 세어 a1을 주고, 점화식 an=can−1+b(n≥2)의 특성방정식t−c=0을 세운다. 그 근 c로 일반항을 an=pcn+q(n≥1) 꼴로 놓는다. 교과서의 계수 c는 이 글의 r이고, 이 글의 c는 고정점이다. 문자가 겹치므로 기호를 옮길 때 주의한다.
식 (4)를 풀어 쓰면 (a0−c)rn+c이므로, 0부터 셀 때는 교과서 꼴의 p=a0−c, q=c에 해당한다. 그래서 고정점을 먼저 구하지 않아도 처음 두 값으로 p,q를 정할 수 있다. 식 (1)의 a0=2, a1=7을 an=p⋅2n+q에 넣으면
p+q=2,2p+q=7.(6)
두 식을 빼면 p=5이고, 그러면 q=−3이다. 식 (3)과 같은 결과이며, q=−3이 바로 고정점이다.11 교과서는 c=0, c=1일 때 이 꼴을 쓴다. 이 글에서 r=0,1을 요구하는 것과 같은 조건이다.
번호가 1부터 시작하면 일반항의 계수와 지수는 어떻게 맞출까?
첫 값이 a1이면 an까지 규칙을 n−1번 적용한다. 그래서 식 (4)처럼 처음 값과 고정점의 차를 계수로 두면 지수가 n−1이 된다. 식 (4)에서 a0를 a1로, rn을 rn−1로 바꾼다.
그림 3에서 hn+1은 2, 4, 8, 16, 32로 두 배씩 커진다. 첫 칸 n=1에서 규칙을 적용한 횟수는 0번이므로, 계수를 h1−c=2로 둔 식 (8)의 지수에는 n이 아니라 n−1이 들어간다. 원판 10개면 식 (8)로 210−1=1023번이다.
교과서처럼 hn=p⋅2n+q(n≥1)로 두면 지수는 n 그대로이고 계수 p가 그 차이를 맡는다. h1=1, h2=3을 넣은 2p+q=1, 4p+q=3에서 p=1, q=−1이므로 같은 식 2n−1이 나온다. p=(h1−c)/2라서 두 꼴은 같은 식을 다르게 쓴 것이다.
그림 3 하노이의 탑 이동 횟수 h1=1, hn+1=2hn+1의 처음 다섯 값이다. 고정점 −1을 뺀 hn+1은 두 배씩 커지고, 첫째 값에서 규칙을 적용한 횟수는 n−1이다. figures/hanoi_index.py
항의 차가 주어지면 무엇을 더할까?
an+1−an=f(n)의 양변을 번호 0부터 n−1까지 더하면 가운데 항들이 지워진다. n≥1에서
an=a0+k=0∑n−1f(k).(9)
예를 들어 a0=4이고 증가량이 2n+1이면 첫 변화량은 1, 다음은 3, 그다음은 5다. 첫 세 번을 적용한 값은 4+1+3+5=13이다. 일반적으로 2k+1=(k+1)2−k2이므로 이 차들을 더하면 n2만 남아 an=4+n2다. n=0일 때도 직접 넣어 처음 값 4를 확인한다. 합 기호는 시그마의 유한합이다.
그림 4는 처음 값 4 위에 증가량을 차례로 쌓은 모습이다. a3=13은 4 위에 1, 3, 5를 쌓은 높이다. 새로 쌓는 칸이 2씩 커지므로 등차수열의 합이 생기고, 그 합이 n2이다.
그림 4a0=4, an+1=an+2n+1의 처음 다섯 항이다. 처음 값 4 위에 증가량 1, 3, 5, 7이 차례로 쌓여 4+n2인 5, 8, 13, 20이 된다. 채운 칸이 마지막으로 더한 증가량이다. figures/difference_staircase.py
항의 비가 주어지면 무엇을 곱할까?
앞 항에 번호에 따라 바뀌는 수 g(n)을 곱하는 an+1=g(n)an이면, 차를 더하는 대신 비를 곱한다. 처음 값에 곱한 수들을 차례로 모으면 된다.
an=a0g(0)g(1)⋯g(n−1)(n≥1).(10)
a0=3, an+1=n+1n+2an이면 곱하는 수가 12,23,34,…이다. 이웃한 분자와 분모가 약분되어 마지막 분자 n+1만 남는다.
an=3⋅12⋅23⋯nn+1=3(n+1).(11)
차례로 계산한 a1=6, a2=9, a3=12가 식 (11)의 값과 같다. g(n)이 상수 r이면 식 (10)은 등비수열의 a0rn이 된다.
구한 식이 유일한 일반항임은 어떻게 확인할까?
식 (3)에 n=0을 넣으면 2다. 어느 번호 n에서 식이 맞다고 할 때, 규칙을 한 번 적용한 값은 2(5⋅2n−3)+3=5⋅2n+1−3이다. 따라서 처음부터 다음 항으로 계속 이어져 모든 번호에서 맞는다. 이것이 수학적 귀납법의 구조다.
또한 처음 값이 같은 두 수열이 같은 규칙을 따르면 다음 값도 같다. 이를 반복하면 두 수열의 모든 항이 같으므로, 초기 조건까지 만족하는 일반항을 하나 찾으면 그 수열을 정확히 찾은 것이다.
핵심
일차 점화식 an+1=ran+b에서 r,b가 실수 상수이고 n≥0일 때, r=0,1이면 고정점 c=b/(1−r)를 빼서 an=c+(a0−c)rn을 얻는다. r=1,0은 따로 계산하고, 일반항은 처음 값과 모든 번호의 점화식을 함께 만족해야 한다.
Q. 일차 점화식에서 곱하는 계수가 음수여도 고정점 방법을 쓰나요?
그렇다. 상수 r=−1도 r=0,1이므로 사용할 수 있다. a0=1, an+1=−an+4이면 c=2이고 an=2−(−1)n이라서 1과 3이 번갈아 나온다. 식 (5)에서 ∣r∣=1이므로 고정점 2와의 거리는 1에서 바뀌지 않는다.
Q. 일차 점화식에 번호가 들어가면 고정점 공식이 그대로 맞나요?
아니다. an+1=2an+n의 더하는 양은 상수가 아니므로 식 (4)의 가정을 벗어난다. 대신 번호의 일차식만큼 옮기면 an+1+(n+1)+1=2(an+n+1)이 되어, an+n+1이 공비 2인 등비수열이다. a0=1이면 an=2n+1−n−1이고 a3=12다.
Q. 일차 점화식의 몇 항만 맞으면 일반항을 찾은 건가요?
아니다. 처음 다섯 항과 맞아도 여섯째 값부터 어긋나는 식을 만들 수 있다. 계산은 후보를 찾는 데 쓰고, 일반항의 확정에는 처음 값과 모든 번호에 대한 대입을 쓴다.
일차 점화식의 일반항을 구할 때 생기는 오해
식 (4)에 a0 대신 a1만 넣고 지수 n은 그대로 둔다 — 하노이에서 계수 h1−c=2와 지수 n을 함께 쓰면 n=1에서 −1+2⋅21=3이 되어 처음 값 1과 어긋난다. 번호의 시작을 바꾸면 계수나 지수도 함께 맞춘다. 계수를 그대로 두면 식 (7)처럼 지수가 n−1이고, 지수 n을 두면 처음 두 값으로 다시 정한 계수가 p=1이다.
옮긴 수열을 구하면 원래 값이다 — 식 (2)에서는 3을 더해 옮겼으므로 마지막에 3을 빼야 한다. 옮긴 첫 값 5를 원래 첫 값 2와 혼동하지 않는다.
교과서의 c와 이 글의 c는 같은 수다 — 교과서의 c는 곱하는 계수로 식 (1)에서는 2이고, 이 글의 c는 고정점 −3이다. 교과서 꼴 p⋅2n+q에서 고정점에 해당하는 것은 q다.
직접 해보기
a0=3, an+1=2an+5의 일반항과 a3을 구하자.
답
고정점은 c=5/(1−2)=−5다. 따라서 an=−5+8⋅2n이고 a3=64−5=59다. 처음 세 번을 적용하면 11, 27, 59로 일치한다. 교과서처럼 p⋅2n+q로 놓아도 p+q=3, 2p+q=11에서 p=8, q=−5를 얻는다.
차례로 9, −4, −4다. 1번 이후는 모두 −4지만 0번 값이 다르므로 전체 수열은 상수 수열이 아니다.
번호가 1부터인 v1=5, vn+1=3vn−4(n≥1)의 일반항과 v4를 구하자.
답
고정점은 c=−4/(1−3)=2이고 v1−c=3이다. 식 (7)로 vn=2+3⋅3n−1=2+3n이므로 v4=83이다. 차례로 계산한 11, 29, 83과 일치한다.
더 읽기
교육부 고시 제2022-33호 — 별책20 이산 수학 [12이수02-02]와 해설. 이웃한 두 항의 관계를 변형해 일반항을 구하고, 특성방정식의 근을 이용하는 범위다.
우리교과서 『이산 수학』 공개 원문 — 이준열 외, 2022 개정판, 인쇄57–59쪽. 특성방정식 t−c=0과 an=pcn+q의 연립방정식 풀이를 대조했다. ‘교과서의 특성방정식 풀이는 고정점 풀이와 같은 식을 준다’ §가 이 쪽에 기댄다.
Oscar Levin, Solving Recurrence Relations — 『Discrete Mathematics: An Open Introduction』 3판 2.4절. 가운데 항이 지워지는 합(telescoping)과 반복 대입(iteration)을 다룬다. ‘항의 차가 주어지면 무엇을 더할까?’ §와 같은 방법이다.
2026-11-17 · 전수 검수 반영 — 일차 점화식의 정의를 좁히고, 고정점과의 거리·수조 활용, 교과서 특성방정식 풀이와 기호 대응, 1부터 세는 하노이 예, 항의 비, 번호가 든 관계의 이동, 연습 5문항으로 보강하고, 1부터 셀 때 교과서 꼴은 지수 n을 두고 계수로 맞춘다는 대응과 오해 문구를 바로잡음 (에이전트 수정, 그림 1→4)
2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림