【将棋のシンプル数学難問】飛車が左下から右上へ進む場合の数は何通りか

問題

ｎ×ｎの将棋盤上で，飛車を１の１（左下）からｎのｎ（右上）まで
進める動かし方は9^n 通り以下であることを示せ。

ただし，飛車は右または上に一度に何マスでも進むことができ，
方向を変えるとき以外も立ち止まれるものとする。