1
$\begingroup$

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

  • 2
    People are generally more inclined to help if you don't order them to do your work.2011-03-16
  • 0
    many times questions arise from our work!2011-03-16
  • 4
    I think the point was more about the imperative mode than about the work :-)2011-03-16
  • 0
    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.2011-03-16
  • 0
    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$.2011-03-16
  • 0
    We then have, $\sum\limits_{k \geq 0} g_k z^k = \sum \limits_{k \geq 0} (\lambda \frac{1}{2^{k-1}}g_{k-1}-g_{k-1})z^k \Longrightarrow$ $G(z)= \lambda \sum \limits_{k \geq 0} \frac{1}{2^{k-1}}g_{k-1}z^k - z\sum \limits_{k \geq 0} g_{k-1}z^{k-1}\Longrightarrow$ $G(z)= \lambda \sum \limits_{k \geq 0} \frac{1}{2^{k-1}}g_{k-1}z^k - z g_{-1}z^{-1} - z \sum \limits_{k \geq 1}g_{k-1}z^{k-1} \Longrightarrow (g_{-1}=0$ by definition)2011-03-16
  • 0
    $G(z)=\lambda \sum \limits_{k \geq 0} \frac{1}{2^{k-1}}g_{k-1}z^k-zG(z) \Longrightarrow$ $G(z) \frac{1+z}{\lambda} = z (\frac{1}{2^{-1}}g_{-1}z^0)+z\sum \limits_{k \geq1} \frac{1}{2^{k-1}}g_{k-1}z^{k-1} \Longrightarrow (g_{-1}=0$ by definition) $G(z) \frac{1+z}{\lambda} = z\sum \limits_{k \geq 0} g_k (\frac{z}{2})^k \Longrightarrow$ $G(z) \frac{1+z}{\lambda z} = G(z/2) \Longrightarrow$ $G(z) = \lambda \frac{z}{(1+z)(1-\frac{z}{2})} $ (2)2011-03-16
  • 0
    We now have to expand the right part of (2) in a series and find the $i-th$ term. For this we have that $\frac{z}{(1+z)(1-\frac{z}{2})} =z(\frac{A}{1+z} + \frac{B}{1-\frac{z}{2}})$, which gives $A=2/3$ and $B=1/3$.2011-03-16
  • 0
    So we can write (2) in the following way $G(z) = \lambda z (\frac{2}{3}\frac{1}{1+z}+\frac{1}{3}\frac{1}{1-z/2}) \Longrightarrow$ $G(z) = \lambda z(\frac{2}{3}\sum \limits_{k \geq 0} (-1)^k z^k+\frac{1}{3}\sum \limits_{k \geq 0} (\frac{z}{2})^k) \Longrightarrow$ $G(z)= \lambda \sum \limits_{k \geq 0} (\frac{2}{3} (-1)^k z^{k+1}+\frac{1}{3} \frac{z^{k+1}}{2^k}) $ (3) This means that the $k$-th term of $G(z)$ is $g_k=\lambda(\frac{2}{3}(-1)^{k-1}+\frac{1}{3}\frac{1}{2^{k-1}})$, so $A_i=\frac{(n-1)2^n}{3}(2(-1)^{i-1}+\frac{1}{2^{i-1}})$ end of false? approach?2011-03-16
  • 0
    the above $A_i$ is clearly not the correct answer, but where is the mistake?2011-03-16
  • 0
    I do not follow this implication:$$G(z) \frac{1+z}{\lambda z} = G(z/2) \Longrightarrow G(z) = \lambda \frac{z}{(1+z)(1-\frac{z}{2})}.$$ Can you clarify what happened?2011-03-18
  • 0
    @Eric Nitardy: You are so right! $G(z/2) \neq \frac{1}{(1-\frac{z}{2})}$. Instead if I am right we have $G(z)(\frac{1+z}{\lambda z}-1)=-\sum \limits_{k \geq 0} g_k z^k (1-\frac{1}{2^k})$. But how can we solve this? it is like a recursion in generating functions2011-03-18
  • 0
    @Ross Millikan: I think it holds $\frac{A_i}{B_i}=(1-\frac{1}{B_2})(1-\frac{1}{B_3}) \cdots (1-\frac{1}{B_{i-1}})$2011-03-18
  • 0
    No, for example if n=7, all the $B_i$ have a single factor 3, while the product of two terms will have a factor 3^2 in the denominator.2011-03-18
  • 0
    @Ross Millikan: yes you are correct! Say for example $n=7$, then $B_2=3\cdot 2^6$, $B_3=3^2 \cdot 2^{11}$, so say $\frac{A_3}{B_3}=\frac{3^2\cdot 2^{11}-1}{3^2\cdot 2^{11}}=1-\frac{1}{3^2\cdot 2^{11}}$.2011-03-18
  • 0
    @Ross Millikan: But suppose that $\frac{A_i}{B_i}=1-\frac{1}{B_i}$ as you claim, then $A_i=B_i-1$. Take $n=3$. $A_3=B_3-1$ $\Longrightarrow$ $K_1 \cdot K_2=(K_1+1)\cdot(K_2+1)-1$ $\Longrightarrow$ $K_1K_2=K_1K_2+K_1+K_2+1-1$ $\Longrightarrow$ $K_1+K_2=0$ $\Longrightarrow$ $2\cdot 2^2+2\cdot 2^1=2$ which is false.2011-03-19

1 Answers 1