n개의 계단을 오르는 방법의 수를 a_n 이라고 하면

첫번째 발걸음을 한 계단을 오르면 남은 n-1 개의 계단을 오르고

첫번째 발걸음을 두 계단을 오르면 남은 n-2 개의 계단을 오르면 되므로

그리고

위의 두 사건은 서로 배반사건이므로

 a_n=a_{n-1}+a_{n-2}.