Derive an explicit formula for the following recurrence for $n\geq 1$ $a_n = n/2 *a_{n-1}$ is my recurrence
with $a_0 = 1$
What do they mean by an explicit formula and what are the step I should be taking to solve this.
What I have tried so far:
Write out the first 8 terms and try to find a pattern but I didn't really know if this is what I should be doing??
Any help?
Thanks!
 A: Finding an explicit formula means that we need to find a function $f(n)$ such that $a_n=f(n)$. This equation is referred to as the explicit formula. I show in this answer one way to find the explicit form.
Take logarithms on both sides,
$$\ln a_n=\ln (\frac{n}{2})+\ln a_{n-1}$$
$$\ln a_n-\ln a_{n-1}=\ln \frac{1}{2}+\ln n$$
Summing both sides from $n=1$ to $k$ gives,
$$\sum_{n=1}^{k} (\ln a_n-\ln a_{n-1})=\sum_{n=1}^{k} (\ln \frac{1}{2}+\ln n)$$
Notice the left hand side is a telescoping sum. Also notice that:
$$\ln 1+\ln 2+\cdots \ln k=\ln (1 \cdot 2 \cdot \cdots k)=\ln k!$$
This gives, 
$$\ln a_k-\ln a_0=k\ln (\frac{1}{2})+\ln k!$$
Substitute $a_0=1$. 
$$\ln a_k=k\ln (\frac{1}{2})+\ln k!$$
$$a_k=e^{k\ln (\frac{1}{2})+\ln k!}$$
$$a_k=k!\left(\frac{1}{2}\right)^k$$
Or if you prefer, 
$$a_n=n!\left(\frac{1}{2}\right)^n$$
A: \begin{align}
a_n &= \frac n 2a_{n-1}\\
&= \frac n 2\cdot\frac {n-1} 2a_{n-2}\\
&= \frac n 2\cdot\frac {n-1} 2\cdot\frac {n-2} 2a_{n-3}\\
&\!\!\!\quad\vdots\\
&=\frac n 2\cdot\frac {n-1} 2\cdot\frac {n-2} 2\cdots\frac 12a_0\\
&= \boxed{\frac{n!}{2^n}}
\end{align}
