2010학년도 대학수학능력시험 9월 모의평가 수리 영역 가형 공통 10번

두 자연수 $m,n\ (2\le m\le n)$에 대하여 1부터 $n$까지 자연수가 하나씩 적혀 있는 $n$장의 카드 중에서 동시에 $m$장을 선택할 때, 카드에 적힌 어느 두 수도 연속하지 않는 경우의 수를 $N(n,m)$이라 하자.

9장의 카드에서 3장의 카드를 선택할 때, 9가 적힌 카드가 선택되는 경우와 선택되지 않는 경우로 나누면 $N(9,3)$에 대하여 다음 관계식을 얻을 수 있다.

또한 $N(8,3)$을 8이 적힌 카드가 선택되는 경우와 선택되지 않는 경우로 나누어 적용하면

이다. 이와 같은 방법을 계속 적용하면

이다. 여기서

이므로

이다.