たくさんの解答をありがとうございます。
>>508 様の、n=1のときから順番に考えていくというのは分かりますが、
「漸化式」、「漸化式を解く」というのは分かりません。

じつはこの問題は順列、組み合わせ、重複順列、重複組み合わせの応用問題の欄にあるので、
うまい解釈をすればこれらの応用だけで解けるのかもしれないと思います。