# 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

## 1 Answer

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$$.

• I understand everything you said above but the 3 in front of n! is messing up my proof. 3n! = (n)(n - 1)(n - 2)(n - 3) for n > 3 This works if that 3 isn't there, or am I not thinking about this the correct way? – Raz-Al Pool Mar 16 at 20:22
• @Raz-AlPool: What are you substituting for $T(n-3)$? – Brian M. Scott Mar 16 at 20:30
• Wouldn't the (n - 3) just be added on to the factor of n^3 - 3n^2 + 2n The factor is n(n-1)(n-2) so would it become n(n-1)(n-2)(n-3)? I'm still a bit confused as to what I'm supposed to be substituting in the inductive step. – Raz-Al Pool Mar 16 at 20:41
• @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
• Would that just be 3(n - 3)! – Raz-Al Pool Mar 16 at 21:19