I can't find a cool name for this!

Algebra Level 3

( 1 + x ) ( 1 + x 2 ) ( 1 + x 4 ) … ( 1 + x 128 ) = ∑ r = 0 n x r (1+x)\big(1+x^2\big)\big(1+x^4\big) \ldots \big(1+x^{128}\big) = \displaystyle \sum_{r=0}^n x^r

Given the above equation, what is n ? n?


The answer is 255.

View wiki
Shivamani Patil by shivamani patil , 21, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Nihar Mahajan
Apr 26, 2015

The given product can be written as:

( 1 + x ) ( 1 + x 2 ) ( 1 + x 4 ) … ( 1 + x 128 ) = 1 ( x n + 1 − 1 ) x − 1 \large(1+x)(1+x^2)(1+x^4)\dots(1+x^{128})=\dfrac{1(x^{n+1}-1)}{x-1}

We observe that as ( x − 1 ) (x-1) goes to L . H . S L.H.S provided that ( x ≠ 0 , 1 ) (x \neq 0,1) , the L . H . S L.H.S gets compressed to ( x 256 − 1 ) (x^{256} -1) due to identity : a 2 − b 2 = ( a + b ) ( a − b ) a^2-b^2 = (a+b)(a-b) .Thus , the equation takes a new form :

x 256 − 1 = x n + 1 − 1 ⇒ 256 = n + 1 ⇒ n = 255 \Large x^{256}-1 = x^{n+1}-1 \\ \Large\Rightarrow 256 = n+1 \\ \Rightarrow \Large\boxed{n=255}

10 Helpful 0 Interesting 0 Brilliant 0 Confused

Moderator note:

Good. Does this satisfy for all x x ?

It technically works for the case where x = 0. When x = 0, LHS = 1. (Proof not needed for this point right?) RHS = 0 0 + 0 1 + . . . + 0 n 0^0 + 0^1 + ... + 0^n = 1 since 0 0 0^0 = 1. Thus, LHS = RHS, the equations holds true ∀ x∈R.

Marvin Chong - 1 year, 4 months ago

Log in to reply

Indeed, if you define 0 0 : = 1 0^0:=1 , it holds. And in certain contexts, it is defined that way, but not always. It's actually an indeterminate expression (Google tells you it's 1, W|A disagrees). If you would like to read more about this, see the Wikipedia entry on it and this post on MAA .

Though, I agree with you here since this problem is under algebra where the expression is almost always taken to be 1 1 .

Prasun Biswas - 1 year, 4 months ago

The equation is satisfied ∀ x ∈ R ∖ { 0 } \forall~x\in\Bbb{R}\setminus\{0\} . But the method Nihar showed ignores the case of x = 1 x=1 where the finite GP sum formula cannot be used to sum up RHS like that. For completeness, all the cases need to be analyzed. He showed the case where x ∈ R ∖ { 0 , 1 } x\in \Bbb{R}\setminus\{0,1\} . I'll verify it for the case x = 1 x=1 .

x = 1 ⟹ ∏ k = 0 7 ( 1 + 1 ) = ∑ r = 0 n 1 ⟹ 2 8 = n + 1 ⟹ n = 255 x=1\implies \prod_{k=0}^7(1+1)=\sum_{r=0}^n1\implies 2^8=n+1\implies n=255

Hence, the given equation holds ∀ x ∈ R ∖ { 0 } \forall~x\in\Bbb{R}\setminus\{0\} when n = 255 n=255 .

There's another approach for the case of x ≠ 1 x\neq 1 which is almost equivalent to his solution but uses a certain identity to convert LHS into RHS form after the "compression" of LHS is done. The identity is:

x n − y n = ( x − y ) ( ∑ k = 0 n − 1 x n − 1 − k y k ) x^n-y^n=(x-y)\left(\sum_{k=0}^{n-1}x^{n-1-k}y^k\right)

Prasun Biswas - 6 years, 1 month ago

Log in to reply

Right hand side equals to x 0 + x 1 + x 2 + … + x n x^0 + x^1 + x^2 + \ldots + x^n . Are you sure all values of x x satisfy the equation?

Brilliant Mathematics Staff - 6 years, 1 month ago

Log in to reply

Right! I missed the case of x = 0 x=0 . Fixed! Thanks! :)

Prasun Biswas - 6 years, 1 month ago
Magne Myhren
Apr 30, 2015

If the equation holds for all x x , the order of the polynomial on both sides is the same. It is therefore sufficient to multiply the last term in each parenthesis in the L.H.S. product: x × x 2 × x 4 × ⋯ × x 128 = x 1 + 2 + 4 + ⋯ + 128 = x 255 x \times x^{2}\times x^{4} \times \dots \times x^{128}=x^{1+2+4+\dots+128}=x^{255} Hence n = 255 n=255 .

3 Helpful 0 Interesting 0 Brilliant 0 Confused
Steven Lee
Apr 27, 2015

Just a quick thing, is it just me or am I the only one who doesn't see that 1 + x 4 1+x^4

2 Helpful 0 Interesting 0 Brilliant 0 Confused
Chew-Seong Cheong
Apr 26, 2015

I solved this by induction:

( 1 + x ) ( 1 + x 2 ) ( 1 + x 4 ) ( 1 + x 8 ) . . . ( 1 + x 128 ) = ( 1 + x + x 2 + x 3 ( = 2 ˙ 2 − 1 ) ) ( 1 + x 4 ) ( 1 + x 8 ) . . . ( 1 + x 128 ) = ( 1 + x + x 2 + x 3 + x 4 + x 5 + x 6 + x 7 ( = 2 ˙ 4 − 1 ) ) ( 1 + x 8 ) . . . ( 1 + x 128 ) = ( 1 + x + x 2 + x 3 + . . . + x 15 ( = 2 ˙ 8 − 1 ) ) ( 1 + x 16 ) . . . ( 1 + x 128 ) = 1 + x + x 2 + x 3 + . . . + x 255 ( = 2 ˙ 128 − 1 ) (1+x)(1+x^2)(1+x^4)(1+x^8)...(1+x^{128}) \\ = (1+x+x^2+x^{3\color{#D61F06}{(=2\dot{}2-1)}})(1+x^4)(1+x^8)...(1+x^{128}) \\ = (1+x+x^2+x^3+x^4 + x^5 + x^6 +x^{7\color{#D61F06}{(=2\dot{}4-1)}})(1+x^8)...(1+x^{128}) \\ = (1+x+x^2+x^3+...+x^{15\color{#D61F06}{(=2\dot{}8-1)}})(1+x^{16})...(1+x^{128}) \\ = 1+x+x^2+x^3+...+x^{255\color{#D61F06}{(=2\dot{}128-1)}}

⇒ n = 2 ˙ 128 − 1 = 255 \Rightarrow n = 2\dot{}128-1 =\boxed{255}

2 Helpful 0 Interesting 0 Brilliant 1 Confused

Moderator note:

This is not induction.

The moderator is right but ironically passive-aggressive lol

Nathan Richardson - 1 year, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...