# Can't prove the base case for an induction proof

This question is part math and part computer science. But since it is mainly about an induction proof, I guess I'll post it here.

I have a recursive algorithm where the time complexity is expressed with this formula:

$T(n)=T(n-1)*n$

I need to find the exact bound of the algorithm using big Theta notation $\Theta()$

It's fairly easy to see that $T(n)\in\Theta(n!)$

I use induction to prove it. It is the base case which troubles me, so let's skip it for now. Let's assume I have proven the formula for some number $n$.

So, assuming $T(n)=T(n-1)*n=n!$ I have to prove now:

$T(n+1)=T(n)*(n+1)=(n+1)!$

Using the assumption, I just replace $T(n)$ with $n!$ and get:

$T(n+1)=n!*(n+1)=(n+1)!$

Now, back to the base case. Let's use $n=0$.

I get $T(0)=T(0-1)*0=0=1=0!$, which is a contradiction.

Let's use $n=1$:

$T(1)=T(1-1)*1=T(0)*1=0*1=0=1=1!$, I think you can see my problem now.

No matter what number I use as the base case, I get $0=x$ with $x\neq 0$.

Even though I have proven the formula for $n+1$ I cannot prove it for a starting $n$.

Does that mean $T(n)\notin\Theta(n!)$ ?

Or is induction the incorrect way of proving this?

• I think you're missing what the starting value $\;T(0)\;$ is: why do you assume it is zero? Is it given? Perhaps the recursive formula is only valid for $\;n\ge 2\;$ or something. I think this question's lacking information. – DonAntonio Oct 23 '16 at 11:45
• It seems easier to write $T(n+1)=T(n)*(n+1)$ for your algorithm. – Dietrich Burde Oct 23 '16 at 11:48
• @DonAntonio: I don't have to use $n=0$ as a base case, but even if I use, let's say, $n=100$, I always will come back to $T(0)$ which will always be $0$. – Arthur Oct 23 '16 at 11:48
• @DonAntonio: There is no additional information to this assignment. It just says: Find a function $f$, such that $T(n)=T(n-1)*n\in\Theta(f)$ – Arthur Oct 23 '16 at 11:54
• @Arthur So then you have also to come up with $\;T\;$ , not only with $\;f\;$ ? That looks weird... – DonAntonio Oct 23 '16 at 12:01

Observe that for a constant $\;k\in\Bbb R\;$ , we have that
$$T(n)=kn!=\Theta(n!)\iff\;\text{there exist constants}\;\;k_1,k_2\in\Bbb R\;\;s.t.\;\;$$
$$k_1\le\frac{T(n)}{n!}\le k_2$$