높이 1에서 출발해 높이 3에 도착하는 길을 센다. 첫걸음은 위나 아래로 한 칸 움직이고, 그다음부터는 제자리에 머물러도 된다. 단, 어느 순간에도 높이가 0 아래로 내려가면 안 된다. 이렇게 n걸음 만에 도착하는 길의 수가 OEIS A026124의 a(n)이다.
두 걸음이면 1→2→3이라는 길 하나뿐이고, 세 걸음이면 두 가지가 있다. 걸음 수가 늘어날수록 모든 길을 직접 나열하기는 번거로워진다. Mathar가 2013년에 적어 둔 점화식은 앞선 값들을 이용해 다음 값을 계산하게 해 주는데, 나는 이 식의 증명과 정확한 시작 지수를 확인하는 작업을 진행했다. 초반에 식의 값이 0이 되지 않는 경우까지 남겨 두는 데 초점을 맞췄다.
앞선 다섯 값을 쓰는 식과 시작 지수
검토한 점화식은 현재 항과 앞선 다섯 항을 묶는다.
(n+6)a(n) + (−5n−19)a(n−1)
+ 4n a(n−2) + 8(n+1)a(n−3)
+ (−5n+22)a(n−4) + 3(5−n)a(n−5) = 0
a(0)=a(1)=0으로 두면 이 식은 모든 n≥5에서 성립한다. 0걸음이나 한 걸음으로 높이 1에서 3까지 갈 수 없으므로, 두 초기값은 경로의 정의에도 맞는다. a(0)부터 a(4)까지는 0, 0, 1, 2, 7이며, 다음 항의 계수 n+6이 0이 아니어서 이후 값이 하나씩 결정된다.
OEIS에 원래 나열된 값은 n=2부터 시작한다. 그 범위의 항만 사용하려면 가장 먼 항인 a(n−5)도 n−5≥2를 충족해야 하므로 n≥7이라고 쓰면 된다. n≥5와 n≥7은 서로 다른 점화식이 아니라, 앞의 두 값을 명시적으로 보충하느냐의 차이다.
더 앞까지 계산을 맞춰 보기 위해서만 음수 지수의 a(k)도 0으로 두었다. 그러면 식의 왼쪽은 n=2, 3, 4에서 각각 8, −16, 8이 되고, 나머지 n≥0에서는 0이다. 특히 n=4에서 8이 남으므로, 우변이 0인 식을 n=4부터 적용하면 틀린다. 이 세 값을 한꺼번에 설명하는 것이 경계항이다.
경로를 하나의 식으로 모았다
몇백 개의 값을 대입해 맞는지 보는 것만으로는 모든 n에 대한 증명이 되지 않는다. 그래서 원하는 점화식을 전제로 삼지 않고, 경로를 세는 정의에서 생성함수로 이어지는 과정을 적었다. 생성함수 F(z)는 각 a(n)을 zⁿ의 계수로 모아 둔 식이다. 여기서 z는 길이를 표시하는 기호로, 특정 실숫값을 넣을 필요는 없다.
중간에 쓰는 M(z)는 높이 0에서 출발해 음수 높이로 내려가지 않고 다시 0으로 돌아오는 Motzkin 경로의 생성함수다. 그런 경로는 빈 경로, 처음에 제자리에 머무는 경로, 위로 올라갔다가 처음 돌아오는 구간을 가진 경로로 나눌 수 있어 M = 1 + zM + z²M², M(0)=1을 얻는다.
높이 0에서 h까지 가는 경로는 각 높이를 마지막으로 올라가는 지점에서 나누면 zʰMʰ⁺¹로 표현된다. 이를 높이 1에서 3으로 가는 경로에 연결하고, 첫걸음이 제자리인 경우를 빼면 F(z) = z²(1−z)²M(z)⁴가 나온다. 이 생성함수 자체는 이미 OEIS에 있던 결과다. 작업에서는 경로의 첫걸음 조건이 이 식에 어떻게 반영되는지까지 연결했다.
초반의 세 예외를 지우지 않았다
다음으로 F와 그 도함수 F′ 사이의 관계를 다음과 같이 정리했다.
zP(z)F′(z) + Q(z)F(z) = 8z²(1−z)²
여기에 쓰인 다항식은 P(z) = 1−5z+4z²+8z³−5z⁴−3z⁵와 Q(z) = 6−24z+8z²+32z³+2z⁴다. 우변을 전개하면 8z²−16z³+8z⁴가 된다. 바로 이 계수들이 앞에서 남겨 둔 8, −16, 8이며, 5차항부터는 우변의 계수가 모두 0이다.
도함수는 zⁿ의 계수에 n을 곱하면서 차수를 하나 낮춘다. 따라서 P의 j차 계수를 Pⱼ, Q의 j차 계수를 Qⱼ라고 하면, 왼쪽에서 a(n−j)에 붙는 계수는 (n−j)Pⱼ + Qⱼ다. j=0부터 5까지 대입하면 처음의 여섯 계수가 그대로 나오고, 우변의 차수가 4이므로 n≥5라는 범위도 함께 정해진다. 경계항을 없애 버렸다면 초반 값뿐 아니라 식을 적용할 수 있는 범위도 잘못 적게 된다.
미분 관계는 몇몇 z값에서만 확인한 식이 아니다. 공개한 인증서에는 M과 F 사이의 대수적 관계를 연결하는 다항식 항등식, 그리고 그 관계를 위 미분식으로 바꾸는 두 번째 항등식을 적었다. 전개한 모든 정수 계수를 비교할 수 있는 형태다. 마지막에 약분하는 형식적 멱급수의 상수항이 −1이라는 점도 확인했다. 상수항이 0이 아니어서 역수를 갖기 때문에 가능한 약분으로, 0이 될 수 있는 식을 근거 없이 나누는 단계를 피했다.
기존 방법과의 관계도 함께 확인했다
이 미분식은 새로운 일반 이론에서 나온 것은 아니다. Mathar의 2021년 논문은 다항식의 제곱근을 포함하는 생성함수에서 이런 미분 관계를 얻는 일반 공식을 제시한다. A026124의 생성함수를 그 공식에 넣으면, 여기서 쓴 식의 양변에 공통 인자 −4z⁵(1−z)²를 곱한 결과와 정확히 일치한다. 공개 증명에는 그 대입과 인자 제거도 적었다.
9월 5일 공개 자료를 Mathar에게 보내 증명과 시작 지수, 앞선 A026124 전용 증명의 존재 여부를 물었다. 이후 받은 회신에서 그는 이 점화식들이 이미 널리 알려진 방법으로 성립하는 결과라고 지적하며, 자신의 2021년 논문과 Ekhad·Yang·Zeilberger의 2017년 논문을 제시했다. 이 의견을 반영해, 이 작업은 기존 방법을 구체적인 식과 경계항까지 풀어 쓴 인증으로 설명한다. 새로운 난제를 처음 해결했다는 주장으로 넓히지 않는다.
2026년 9월 7일 확인한 OEIS 본문에는 이 식이 D-finite 점화식으로 표시돼 있다. 다만 이 표기를 내 증명의 채택이나 최초 증명에 대한 인정으로 해석하지는 않는다. 내가 공개한 결과의 범위는 경로 정의에서 출발하는 증명, 정확한 시작 지수, 다시 점검할 수 있는 다항식 인증서다.
계산으로 확인한 범위
배포 패키지의 점검에서는 경로를 직접 세는 동적 계획법, 생성함수 전개, 점화식 계산이 n=0부터 256까지의 257개 항에서 일치했다. 그중 우변이 0인 점화식은 n=5부터 256까지 252개 경우를 확인했고, OEIS에 실린 n=2부터 28까지의 27개 값도 대조했다. 길이 10까지는 총 59,049개의 원시 걸음 선택을 열거한 뒤 경로 조건으로 걸렀다. 이 수는 유효한 경로의 개수가 아니라, 검사 전의 선택 전체를 센 값이다.
계수나 초기값, 경계항을 일부러 바꾼 여섯 가지 잘못된 입력이 거부되는지도 점검했다. 이 계산들은 구현을 확인하는 수단이고, 모든 n에 대한 결론은 경로 분해와 항등식, 계수 비교로 증명했다. 둘을 같은 근거로 세지 않았다.
나는 대상 점화식을 정하고 작업 범위와 검증을 요청했다. 기호 유도와 증명문, 점검 코드 및 계산에는 ChatGPT와 Codex가 기여했으며, 역할을 공개 증명·코드 패키지에 기록했다. 이 패키지는 2026년 9월 5일 공개한 기술 노트다.