Closed form formula for the given product

Question

I'm working on a recurrence which give me the following solution:

$$ f(n)=(2+1)(2+\tfrac12)(2+\tfrac13)\cdots\left(2+\tfrac1{\lg(n)}\right) $$

so for $n=16$, $f(n)$ is just like:

$$ (2+1)(2+\tfrac12)(2+\tfrac13)(2+\tfrac14) $$

since $\lg(16)=4$. Does anyone know a way to find a closed-form formula for such kind of product? Perhaps someone know a useful source of theory for such kind of problems?

FYI the recurrence is $C_n=\left(2+\frac1{\lg(n)}\right)C_{n/2}$ for $n\ge2$ and $C_1=1$, $N$ is a power of $2$..

Thanks

Answer 1

Let $N=\log_2 (n)$ be a positive integer (which means that $n=2^k$ where $k$ is a positive integer).

Then, noting that $$\begin{align}\prod_{n=1}^{N}(2n+1)&=3\cdot 5\cdots (2N+1)\\&=(2N+1)!!\\&=\frac{1\cdot 2\cdots (2N)\cdot (2N+1)}{2\cdot 4\cdots (2N-2)\cdot (2N)}\\&=\frac{(2N+1)!}{2^N\cdot (1\cdot 2\cdots (N-1)\cdot N)}\\&=\frac{(2N+1)!}{2^N\cdot N!}\end{align}$$

we can see that your product can be represented as $$\begin{align}\prod_{n=1}^{N}\left(2+\frac 1n\right)&=\frac{\prod_{n=1}^{N}{(2n+1)}}{\prod_{n=1}^{N}n}\\&=\frac{1}{N!}\cdot \frac{(2N+1)!}{2^N\cdot N!}\\&=\frac{2N+1}{2^N}\cdot \frac{(2N)!}{N!N!}\\&=\frac{2N+1}{2^N}\binom{2N}{N}\\&=\frac{2\log_2(n)+1}{n}\binom{2\log_2(n)}{\log_2(n)}.\end{align}$$

Answer 2

the formula is:
$$ f(n)=(2+1)\cdot(2+\frac{1}{2})\cdot(2+\frac{1}{3})\cdots(2+\frac{1}{\log_2(n)}) $$ it can be written as: $$ f(n)=\prod_{i=1}^{\log_2(n)}\Big(2+\frac{1}{i}\Big)=\prod_{i=1}^{\log_2(n)}\Big(\frac{2i+1}{i}\Big)=\frac{\prod_{i=1}^{\log_2(n)}\Big(2i+1\Big)}{\prod_{i=1}^{\log_2(n)}\Big(i\Big)}=\frac{\prod_{i=1}^{\log_2(n)}\Big(2i+1\Big)}{\log_2(n)!} $$ so: $$ f(n)=\frac{\prod_{i=1}^{\log_2(n)}\Big(2i+1\Big)}{\log_2(n)!} $$

---

now on the numerator we have a product of odd numbers, let's find a closed form formula for it:
$$ \prod_{i=1}^{n}\Big(2i+1\Big) =1\cdot3\cdot5\cdots(2n+1)= \frac{ 1 \cdot 2 \cdot 3 \cdot 4 \cdots \cdot (2n+1) }{2\cdot 4 \cdot 6 \cdots (2n)} = \frac{ (2n+1)! }{2^n \left( 1\cdot 2 \cdot 3 \cdots n \right)} = \frac{(2n+1)!}{2^n n!} $$

---

back-substitute adapting the upper bound ($n \rightarrow log_2(n)$) and a bit more algebra and you'll obtain: $$ f(n)=\frac{\prod_{i=1}^{\log_2(n)}\Big(2i+1\Big)}{\log_2(n)!}=\frac{(2log_2(n)+1)!}{n(log_2(n)!)^2} $$