'Transforming' a function $T(m,n)$ into $a(n)$ in an inductive proof

Question

I'm trying to perform an inductive proof for a homework question but am stuck at a scenario I've never encountered before.

I am trying to prove inductively that

$$ T(m,n) = (m + 1 + n)\cdot a(n) - n! $$

where

$$a(n) = \begin{cases} n(a(n - 1) + 1) &, n \geq 1 \\ 0 &, n = 0\end{cases}$$

We already know the following identity:

$$T(m,n) = \begin{cases} n(T(m+1,n-1) + m + 1 + n) &, n > 1 \\ m + 1 &, n = 1\end{cases}$$

I have done the base case n = 1 pretty easily where they both evaluate to $m + 1$, but for the inductive step, I'm completely stuck. How can I get $a(n)$ into my equation to get this inductive step to work? The hardest part for me to understand is how to work with these recursive functions.

Thanks for any help. A complete answer is not necessary, but feel free to take liberties if you find the problem interesting.

Answer 1

Assume that for all $k\le (n-1)$, $P(n):=\{T(m,n)=(m+1+n)a(n)-n!$, for all $m\in\mathbb{N}\}$ is true.

We prove $P(n)$. For $m\in\mathbb{N}$, $$T(m,n)=n(T(m+1,n-1)+m+1+n) \\= n(\ ((m+1)+1+(n-1))a(n-1)-(n-1)!+m+1+n\ ) \\= n((m+1+n)a(n-1)-(n-1)!+m+1+n) \\= n((m+n+1)a(n-1)+(m+n+1))-n! \\= (m+n+1)a(n)-n!$$