ありがとうございます！
なんとか解けました

いわゆる「おととい帰納法」ですね。
n=k,k+1のときの成立を仮定したときにn=k+2のときも成立していればすべてのnについて必ず成立するということを利用しましょう。
ちなみにその下の京大の問題は「強化帰納法」で解けると思います。n=1,2,3,…,kのときの成立を仮定したときにn=k+1のときも成立していればO.K.というやり方ですね。