Consider the following recurrence:
$P(1) = 3$
$P(n) = 3nP(n-1)$
I have to find a closed form for this recurrence. Expanding it a bit, we get:
$$P(n) = 3nP(n-1) = 3n(3(n-1)P(n-2)) = 3n(3(n-1)3(n-2)P(n-3)) = 3^3n(n-1)(n-2)P(n-3)$$
The pattern looks something like $P(n) = 3^kP(n-k)$, however it is missing those terms in between. How to genelarize them in this case? It reminds me of factorial, but it is still blurry to me.
Any help is appreciated.
Your enumeration suggests, after backwards-iterating $k$ times to the $P(n-k)$ term,
$$P(n) = 3^k n^{\underline k} P(n-k)$$
Here, $n^{\underline k}$ is the Pochhammer symbol - it denotes a falling factorial when used like this, which is like a factorial that doesn't finish. You can express it in several equivalent ways depending on preference, experience, and handiness:
$$n^{\underline k} = \underbrace{n(n-1)(n-2)\cdots (n-k+1)}_{\text{total of k factors}} = \prod_{i=0}^{k-1} (n-i) = \frac{n!}{(n-k)!} = P(n,k) = \; _nP _k$$
You can read up more on the Pochhammer symbol on Wikipedia.
In any event, the pattern is clear, and suggests, once you set $k=n-1$ to get to your initial condition of $P(1)=3$, the above expressions simplify and you would see
$$P(n) = 3^{n-1} \cdot n! \cdot P(1) = 3^n \cdot n!$$
What I'll leave up to you: verify that this does in fact work. You can prove this by induction on $n$.
