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