0
$\begingroup$

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 :)

$\endgroup$
2
  • $\begingroup$ 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.$$ $\endgroup$ – J.G. Mar 16 at 19:38
  • 1
    $\begingroup$ All you have to do is to confirm that $3\times n!$ satisfies the same recursion and the same initial conditions as $T(n)$. $\endgroup$ – lulu Mar 16 at 19:41
0
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ 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? $\endgroup$ – Raz-Al Pool Mar 16 at 20:22
  • $\begingroup$ @Raz-AlPool: What are you substituting for $T(n-3)$? $\endgroup$ – Brian M. Scott Mar 16 at 20:30
  • $\begingroup$ 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. $\endgroup$ – Raz-Al Pool Mar 16 at 20:41
  • $\begingroup$ @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)$? $\endgroup$ – Brian M. Scott Mar 16 at 20:47
  • $\begingroup$ Would that just be 3(n - 3)! $\endgroup$ – Raz-Al Pool Mar 16 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.