Prove that $\displaystyle \forall n \epsilon N, \prod_{i=1}^{n}(1+x^{2^i})<\frac{1}{1-x} $

0<x<1

I know of 2 proofs. One, which is mine, and anouther that is better. Try to find both!

Printable View

- Feb 16th 2011, 01:06 PMChris11Inequality puzzle
Prove that $\displaystyle \forall n \epsilon N, \prod_{i=1}^{n}(1+x^{2^i})<\frac{1}{1-x} $

0<x<1

I know of 2 proofs. One, which is mine, and anouther that is better. Try to find both! - Feb 17th 2011, 12:29 AMOpalg
I think the problem looks better if the product start at i=0 rather than i=1. That makes the product bigger, but it's still less than $\displaystyle \frac{1}{1-x}$.

Use the difference of two squares: $\displaystyle (1-x^{2^i})(1+x^{2^i}) = 1-x^{2^{i+1}}$. Therefore

$\displaystyle \prod_{i=0}^{n}(1-x^{2^i})\prod_{i=0}^{n}(1+x^{2^i}) = \prod_{i=1}^{n+1}(1-x^{2^i})$. Divide both sides by $\displaystyle \prod_{i=1}^{n}(1-x^{2^i})$ to get

$\displaystyle (1-x)\prod_{i=0}^{n}(1+x^{2^i}) = 1-x^{2^{n+1}} < 1$.

Is that your proof, or is it better? (Wondering) - Feb 17th 2011, 08:11 AMChris11
That's actualy neither! I like it though. My proof expaned the darn polynomial via induction, showing that the coefficents were all one. Then, I subtracted that expansion from the geometric series for $\displaystyle \frac{1}{1-x}$. The slicker proof is just a multiplication by (1-x) ! You didn't have to multiply by that product. Of course, you can do a lot to the exponent and maintain that inequality!

- Feb 17th 2011, 08:58 AMmelese
Write $\displaystyle S=\prod_{i=0}^{\infty}(1+x^{2^i})$. (Only later did I notice that it's actually $\displaystyle n$ and not $\displaystyle \infty$, but I wanted to post this anyway.)

If we expand the infinite product $\displaystyle S $, a typical term is $\displaystyle x^N$, where $\displaystyle N $ is a sum of powers of two.

The following is the**Basis Representation Theorem**for base two.

*Every*positive integer $\displaystyle N $ can be represented*uniquely*as the sum of powers of two. Example: $\displaystyle 5=2^2+2^0$.

Since the exponents of the terms in the infinite series $\displaystyle S $ consist of*all possible combinations*of powers of two, it follows from the theorem that the exponents range over*all*the positive integers.

Therefore, $\displaystyle S=\prod_{i=0}^{\infty}(1+x^{2^i})=1+x^1+x^2+x^3+x^ 4+x^5+\cdots=1/(1-x)$.

We have $\displaystyle \prod_{i=1}^{\infty}(1+x^{2^i})<(1+x)\prod_{i=1}^{ \infty}(1+x^{2^i})=S$, i.e. $\displaystyle \prod_{i=1}^{\infty}(1+x^{2^i})<1/(1-x)$.

Here, $\displaystyle \prod_{i=1}^{n}(1+x^{2^i})<\prod_{i=1}^{\infty}(1+ x^{2^i})<1/(1-x)$.

So, a third one?(Rock) - Feb 17th 2011, 10:28 AMChris11