# Factorial induction proof with recursion, no idea where to go

So I've been stuck on this one problem from my Foundations of Computing class where I'm given a function $$T(n)$$ and the base cases are defined already and a function is given to find the other $$n$$ values greater than the base case. This is how it looks.

Consider the following recursively defined function:

$$T(n)=\begin{cases} 3,&\text{if }n=1\\ 6,&\text{if }n=2\\ 18,&\text{if }n=3\\ T(n-3)(n^3-3n^2+2n),&\text{otherwise.} \end{cases}$$

Use induction to prove that $$T(n)=3(n!)$$ for all $$n\ge 1$$.

I have no clue how to even get started on this. We never covered factorial induction proofs, let alone with recursion in my class so I would really appreciate some help with this.

Thanks :)

• Try factorizing the cubic factor. Then prove by induction that$$T(n)=n!3,\,T(n+1)=(n+1)!3,\,T(n+2)=(n+2)!3.$$ – J.G. Mar 16 at 19:38
• All you have to do is to confirm that $3\times n!$ satisfies the same recursion and the same initial conditions as $T(n)$. – lulu Mar 16 at 19:41

There’s nothing special about the fact that a factorial is involved. It’s immediate from the definition of $$T$$ that $$T(n)=3n!$$ for $$n=1,2,3$$; those are your base cases for this strong induction. For the induction step you simply have to use the definition of $$T$$ to show that if $$T(k)=3k!$$ for $$k=1,\ldots,n-1$$, where $$n>3$$, then $$T(n)=3n!$$. That definition says that
$$T(n)=T(n-3)(n^3-3n^2+2n)\,,$$
so your task is to use the induction hypothesis and a little algebra to show that the righthand side simplifies to $$3n!$$. HINT: It will be helpful to factor $$n^3-3n^2+2n$$.
• @Raz-AlPool: What are you substituting for $T(n-3)$? – Brian M. Scott Mar 16 at 20:30
• @Raz-AlPool: There is no factor of $n-3$: there is a factor of $T(n-3)$. The induction hypothesis says that $T(k)=3k!$ if $1\le k<n$, and we know that $1\le n-3<n$, so what is $T(n-3)$? – Brian M. Scott Mar 16 at 20:47