# compute the fraction of products

Let $A_i=K_1 \times K_2 \times K_3 \times \cdots \times K_{i-1}$ and $B_i=(K_1+1) \times (K_2+1) \times (K_3+1) \times \cdots \times (K_{i-1}+1)$, where $K_{i-1}=(n-1)2^{n-(i-1)}-1$, $i=2,3,\cdots$. Find $a_i=\frac{A_i}{B_i}$ and $\sum_{i=1}^n a_i$.

-
People are generally more inclined to help if you don't order them to do your work. –  Stijn Mar 16 '11 at 8:12
many times questions arise from our work! –  pebox11 Mar 16 '11 at 8:44
I think the point was more about the imperative mode than about the work :-) –  joriki Mar 16 '11 at 9:46
If you reverse the order of your sum, the power of 2 becomes $2^i$. Also, you can write $\frac{A_i}{B_i}=1-\frac{1}{B_i}$. I don't see a simple expression, but the terms get close to 1 quickly so only calculating the lowest several (in my reverse order) will get you quite close. –  Ross Millikan Mar 16 '11 at 13:23
Consider the following idea: Since $B_i$ is easy to compute someone might try to compute $A_i$ using generating functions. Here is an attempt to do this which unfortunately does not work and can not find the mistake. FALSE APPROACH Let $g_1=1$, $g_2=K_1$, $g_3=K_1 \times K_2$, $\cdots$. These terms obey the recurrence relation $g_k=K_{k-1}g_{k-1}=((n-1)2^{n-(k-1)}-1)g_{k-1}$ (1) We can write (1) as $g_k=\lambda \frac{1}{2^{k-1}}g_{k-1}-g_{k-1}$, $\lambda=(n-1)2^n$. –  pebox11 Mar 16 '11 at 19:34

\begin{align} a_i&=\frac{A_i}{B_i}=\prod_{m=1}^{i-1}\left(1-\frac{1}{K_m+1}\right)\\ &=\prod_{m=1}^{i-1}\left(1-\frac{1}{(n-1)2^{n-m}}\right)\\ &=\prod_{m=1}^{i-1}\left(1-\frac{1}{(n-1)2^n}2^m\right)\\ &=\left(\frac{1}{(n-1)2^{n-1}},2\right)_{i-1}, \end{align}
So what you want is the sum $\sum_{i=0}^{n-1}(c_n,q)_{i}$ where $c_n=\frac{1}{(n-1)2^{n-1}}$.
This is exactly a situation for the $q$-Zeilberger algorithm to find a recurrence for the sum. If this works you can use the $q$-Hyper algorithm to check if there is a $q$-hypergeometric solution (which is not very likely because the sum does have two unnatural bounds, so it will be a ${}_3\Phi_2$ that is not Pfaff-Saalschütz).