1. Inequality 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!

2. Originally Posted by Chris11
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 another that is better. Try to find both!
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?

3. 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!

4. Originally Posted by Chris11
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!
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?

5. Originally Posted by melese
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?