Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
2  
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
4  
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
show 11 more comments

1 Answer

$$\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} $$

where I use the notation for the q-Pochhammer symbol.

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.