# Is there a way to simplify this sum $\sum_{i=1}^{h}\prod_{k=1}^i(2^{2^{h-k}} + 1),$?

Like the title says, is there a way to simplify this to some polynomial form or any other form that gets rid of the sum and product?

$$\sum_{i=1}^{h}\prod_{k=1}^i(2^{2^{h-k}} + 1)$$

or this:

$$\sum_{i=1}^{h}\prod_{k=1}^i 2^{2^{h-k}}$$

I have no idea how to approach the first one, but the second one I think it might be possible to turn the product into a sum, but not sure. thanks in advance.

• $\prod_{a=0}^b (x^{2^{a+c}} + 1) = \prod_{a=0}^b ((x^{2^c})^{2^a} + 1) = \sum_{n=0}^{2^{b+1}-1} (x^{2^c})^n$ – reuns Jul 29 '19 at 15:44

## 1 Answer

I was able to simplify the second summation $$\sum_{i=1}^h\prod_{k=1}^i 2^{2^{h-k}}$$:

\begin{align*} j&=h-k\\ k&=1\Rightarrow j=h-1\\ k&=i\Rightarrow j=h-i\\ \sum_{k=1}^i 2^{h-k} &= \sum_{j=h-i}^{h-1} 2^j\\ &= \sum_{j=0}^{h-1} 2^j - \sum_{j=0}^{h-i-1} 2^j\\ &= \frac{2^h-1}{2-1} - \frac{2^{h-i}-1}{2-1}\\ &= 2^h-2^{h-i}\\ \sum _{k=1}^i 2^{h-k} &= 2^h-2^{h-i}\\ \prod _{k=1}^i 2^{2^{h-k}} &= 2^{\sum _{k=1}^i 2^{h-k}} = 2^{2^h-2^{h-i}}\\ \overset{h}{\sum_{i=1} }\prod_{k=1}^i 2^{2^{h-k}}&=\overset{h}{\sum _{i=1} }2^{2^h-2^{h-i}}\\ \\ \\ j&=2^h-2^{h-i}\\ i&=1\Rightarrow j=2^h-2^{h-1}=\left(1-\frac{1}{2}\right) 2^h=\frac{2^h}{2}=2^{h-1}\\ i&=h\Rightarrow j=2^h-2^0=2^h-1\\ \sum_{i=1}^h 2^{2^h-2^{h-i}} &= \sum_{j=2^{h-1}}^{2^h-1} 2^j\\ &=\sum_{j=0}^{2^h-1} 2^j-\sum_{j=0}^{2^{h-1}-1} 2^j\\ &=\frac{2^{2^h}-1}{2-1}-\frac{2^{2^{h-1}}-1}{2-1}\\ &=2^{2^h}-2^{2^{h-1}}\\ &=u-\sqrt{u}\\ \\ \\ \overset{h}{\sum _{i=1} }\prod _{k=1}^i 2^{2^{h-k}}&=u-\sqrt{u} \end{align*} For simplicity I used variable $$u={2^2}^h$$.

• I am afraid you made an error here, "$\sum_{i=1}^h 2^{2^h-2^{h-i}} = \sum_{j=2^{h-1}}^{2^h-1} 2^j$". The equality holds when $h=1,2$. It does not hold otherwise. – Apass.Jack Aug 1 '19 at 6:04
• @Apass.Jack Thanks for pointing that out, why is it wrong though? the variable substitution looks fine to me!. – razzak Aug 1 '19 at 15:51
• How? could you please elaborate. – razzak Aug 1 '19 at 16:00
• Replacing $2^h-2^{h-i}$, the new variable $j$ should loop through $h$ values, $2^h-2^{h-1}, 2^h-2^{h-2}, \cdots, 2^h-2^{2}, 2^h-2^{1}, 2^h-2^0$. Note that these values are not consecutive, i.e. $j$ does not loop from $2^h-2^0$ to $2^h-2^{h-1}$ with step-length 1. – Apass.Jack Aug 1 '19 at 16:06