자연계열 4번

(1)$\displaystyle n=1$인 경우: $\displaystyle f(0)=1$, $\displaystyle f(1)=1$$\displaystyle n=2$인 경우: $\displaystyle f(0)=1$, $\displaystyle f(1)=2$, $\displaystyle f(2)=1$

오른쪽 그림과 같이 왼쪽 아래로 한 칸 이동하는 것을 $\displaystyle a$, 오른쪽 아래로 한 칸 이동하는 것을 $\displaystyle b$라 하면, B에서 $\displaystyle (k,0)$으로 가는 최단경로는 $\displaystyle a$와 $\displaystyle b$형태의 선분만 사용하여 $\displaystyle (k,0)$에 도달해야 하므로 최단경로의 가짓수는 $\displaystyle (n-k)$개의 $\displaystyle a$와 $\displaystyle k$개의 $\displaystyle b$를 일렬로 늘어놓는 순열의 수이다.따라서 $\displaystyle f(k)={}_{n}\mathrm C_k=\frac{n!}{k!(n-k)!}$이다.

(2)$\displaystyle g(n)=\sum_{k=0}^n f(k)=\sum_{k=0}^n{}_{n}\mathrm C_k=2^n$이다.이로부터 $\displaystyle \sum_{n=1}^{\infty}\frac1{g(n)}=\sum_{n=1}^{\infty}\frac1{2^n}=\frac{\frac12}{1-\frac12}=1$이다.

(3)$\displaystyle n^2$개의 합동인 정삼각형으로 분할된 정삼각형 OAB에는 $\displaystyle \sum_{k=1}^{n+1}k=\frac{(n+1)(n+2)}2$개의 꼭짓점이 있다. 한번 지난 점은 다시 지나지 않고 모든 꼭짓점을 지나는 경로가 존재하면 이 경로가 가장 긴 경로이고, 이 경로에는 길이가 1인 선분이 $\displaystyle \frac{(n+1)(n+2)}2-1=\frac{n(n+3)}2$개 있다.이제 점 B에서 점 A로 가는 길이가 $\displaystyle \frac{n(n+3)}2$인 경로가 존재함을 보이자.$\displaystyle x$축과 평행한 선분은 $\displaystyle \frac{n(n+1)}2$개가 있다. $\displaystyle x$축과 평행한 모든 선분을 변 OB 또는 AB위의 $\displaystyle n$개의 선분을 이용해 연결하여 B에서 A로 가는 하나의 경로로 만들면 길이가 $\displaystyle \frac{n(n+3)}2$인 경로가 된다. (다른 형태의 경로를 제시해도 됨)