# Inequality puzzle

• Feb 16th 2011, 01:06 PM
Chris11
Inequality puzzle
Prove that $\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 AM
Opalg
Quote:

Originally Posted by Chris11
Prove that $\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 $\frac{1}{1-x}$.

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

$\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 $\prod_{i=1}^{n}(1-x^{2^i})$ to get

$(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 AM
Chris11
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 $\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 AM
melese
Quote:

Originally Posted by Chris11
Prove that $\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 $S=\prod_{i=0}^{\infty}(1+x^{2^i})$. (Only later did I notice that it's actually $n$ and not $\infty$, but I wanted to post this anyway.)

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

The following is the Basis Representation Theorem for base two.
Every positive integer $N$ can be represented uniquely as the sum of powers of two. Example: $5=2^2+2^0$.

Since the exponents of the terms in the infinite series $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, $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 $\prod_{i=1}^{\infty}(1+x^{2^i})<(1+x)\prod_{i=1}^{ \infty}(1+x^{2^i})=S$, i.e. $\prod_{i=1}^{\infty}(1+x^{2^i})<1/(1-x)$.

Here, $\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 AM
Chris11
Quote:

Originally Posted by melese
Write $S=\prod_{i=0}^{\infty}(1+x^{2^i})$. (Only later did I notice that it's actually $n$ and not $\infty$, but I wanted to post this anyway.)

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

The following is the Basis Representation Theorem for base two.
Every positive integer $N$ can be represented uniquely as the sum of powers of two. Example: $5=2^2+2^0$.

Since the exponents of the terms in the infinite series $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, $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 $\prod_{i=1}^{\infty}(1+x^{2^i})<(1+x)\prod_{i=1}^{ \infty}(1+x^{2^i})=S$, i.e. $\prod_{i=1}^{\infty}(1+x^{2^i})<1/(1-x)$.

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

So, a third one?(Rock)

(Rock)