2.2.10

(機械的にやる方法は分からなかった)

問題文にあるように数列$$T_n$$の最初の項は$$2,3,6,14,40,152,784,5168,40576,363392,\ldots$$である。 指数的に増えているように見えるので、とりあえず 隣り合う項の比を計算すると次のようになる: $$1.5, 2, 2.3, 2.8, 3.8, 5.1, 6.5, 7.9, 9.0, \ldots$$

階乗的に増えてそうなので$$A_n = n!$$としてその差を計算すると以下のようになる。

これを見ると$$T_n = n! + 2^n$$が成り立ちそうなのでこれを帰納法で証明する。

$$n<3$$について成り立つのは表から分かる。 $$n\geq 3$$のとき、 $$\begin{aligned} T_n &=(n+4)T_{n-1}-4nT_{n-2}+(4n-8)T_{n-3}\\ &=(n+4)((n-1)!+2^{n-1})+4n((n-2)! + 2^{n-2})+(4n-8)((n-3)!+2^{n-3})\\ &=((n+4)(n-1)(n-2) + 4n(n-2) + (4n-8))(n-3)!\\ &\;\;\;\;+ (4(n+4) + 8n+(4n-8))2^{n-3}\\ &=n(n-1)(n-2)(n-3)! + 8*2^{n-3}\\ &= n! + 2^n \end{aligned}$$ より示せた。