How to solve this recurrence : $T_{n}=T_{n-1}+ (n)^2 [T_{n-2}+1]$

Question

It is given that $T_1=1$, $T_2= 5$, $T_3 = 23$. I have already proved that it should be $(n+1)! - 1$ by induction. But I am wondering if there is any other way, which involves solving the recursive relation.

Answer 1

$$\begin{align} &\Longleftrightarrow T_n +1 = T_{n-1}+1 + n^2 (T_{n-2}+1 ) \\ &\Longleftrightarrow (T_n +1)- (n+1)(T_{n-1}+1) =- n(T_{n-1}+1) + n^2 (T_{n-2}+1 ) \\ &\Longleftrightarrow (T_n +1)- (n+1)(T_{n-1}+1) =- n \left((T_{n-1}+1) -n (T_{n-2}+1 )\right) \tag{1} \\ \end{align}$$ Denote $x_n = (T_n +1)- (n+1)(T_{n-1}+1)$, then $$\begin{align} (1) &\Longleftrightarrow x_n = -nx_{n-1} =...= (-1)^{n-2} \frac{n!}{2!} x_2 = (-1)^{n-2} \frac{n!}{2!} (6 - 3\cdot 2) = 0 \end{align}$$ Then $$T_n+1 =(n+1)(T_{n-1}+1) =...=\frac{(n+1)!}{2!}(T_1+1) = (n+1)!$$ Q.E.D

Answer 2

I assume that $(n+1)^2$ is a typo and the correct one is $n^2$, according to the first three numbers you mentioned. One way to approach is linear algebra. First of all, simply by adding $1$ to each side, it suffices to solve the recurrence relation given by $$ S_n = S_{n-1} + n^2 S_{n-2}, \qquad S_1 = 2, \quad S_2 = 6, $$ via the substitution $S_n := T_n+1$. Let us look at two equalities with one auxiliary equality. $$ \begin{cases} S_n = S_{n-1} + n^2 S_{n-2} \\[5pt] S_{n-1} = S_{n-1} + 0 \cdot S_{n-2}. \end{cases} $$ This is equivalent to the following equality of matrices. $$ \begin{pmatrix} S_n \\ S_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & n^2 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} S_{n-1} \\ S_{n-2} \end{pmatrix}. $$ Therefore, via the substitution $$ \vec{s}_n = \begin{pmatrix} S_n \\ S_{n-1} \end{pmatrix} \quad \text{and} \quad A_n = \begin{pmatrix} 1 & n^2 \\ 1 & 0 \end{pmatrix}, $$ what we need to solve becomes the recurrence relation given by $$ \vec{s}_n = A_n \vec{s}_{n-1}, \qquad \vec{s}_2 = \begin{pmatrix} 6 \\ 2 \end{pmatrix}. $$ The answer to this is $$ \begin{align*} \vec{s_n} & = A_n A_{n-1} A_{n-2} \cdots A_3 \vec{s}_2, \\[5pt] & = A_n A_{n-1} A_{n-2} \cdots A_3 A_2 A_1 A_0 \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \end{align*} $$ so it remains to compute the matrix $A_n A_{n-1} A_{n-2} \cdots A_0$. There are many ways to find this matrix, but I think the simplest way in this case is to observe the rule by computing a few first terms. $$ \begin{align*} A_0 & = \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix}, \\[5pt] A_1 A_0 & = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 2 & 0 \\ 1 & 0 \end{pmatrix}, \\[5pt] A_2 A_1 A_0 & = \begin{pmatrix} 1 & 4 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 2 & 0 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 6 & 0 \\ 2 & 0 \end{pmatrix}, \\[5pt] & \vdots \\[5pt] A_n \cdots A_0 & = \begin{pmatrix} (n+1)! & 0 \\ n! & 0 \end{pmatrix}. \end{align*} $$ If you are not happy with this argument, you can prove this by mathematical induction of course. Consequently, $$ \begin{pmatrix} S_n \\ S_{n-1} \end{pmatrix} = \vec{s}_n = \begin{pmatrix} (n+1)! & 0 \\ n! & 0 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} (n+1)! \\ n! \end{pmatrix}, $$ which means that $T_n = (n+1)!-1$.

Answer 3

Given that $T_1=1, T_2=5$ and $T_n=T_{n-1}+n^2\left(T_{n-2}+1\right) \textrm{ for }n\geq 3. $

We are going to prove, by Mathematical Induction, that $$ P(n): T_n=(n+1) !-1, $$ where $n\in N.$ Obviously, $(1+1)!-1=1=T_1$ and $(2+1)!-1=5 =T_2.$ Hence $P(1)$ and $P(2) $are true. Now assume that $P(k)$ and $P(k+1)$ are true, then $$ \begin{aligned} T_{k+2} &=T_{k+1}+(k+2)^2\left(T_k+1\right) \\ &=(k+2) !-1+(k+2)^2(k+1) ! \\ &=(k+1) !\left[k+2+(k+2)^2\right]-1 \\ &=(k+1) !(k+2)(k+3)-1 \\ &=(k+3) !-1 \end{aligned} $$ Therefore $P(k+2) $ is also true. By the principle of Mathematical Induction, $P(n)$ is true for all natural number $n.$