2013학년도 사관학교 1차 선발시험 수학 영역 문과 29번

다음과 같이 두 수 $0$과 $1$만을 사용하여 제 $n$행에 $n$자리의 자연수를 크기순으로 모두 나열해 나간다. $(n=1,2,3,\ldots)$

제 $n$행에 나열한 모든 수의 합을 $a_n$이라 하자. 예를 들어, $a_2=21$, $a_3=422$이다.

$\displaystyle\lim\limits_{n\to\infty}\dfrac{a_n}{20^n}=\dfrac qp$일 때, $p+q$의 값을 구하시오. (단, $p,q$는 서로소인 자연수이다.) [4점]