むしろ俺は漸化式を使わないで解いたから漸化式を使ったやり方をぜひ教えて欲しいと思ってるんだけど、
ちなみに俺は組合わせと数学的帰納法で解きました。