Odd coefficients only

For each positive integer nn, find the number of odd coefficients in the expansion of (x2+x+1)n ( x^2 + x + 1) ^ n .


I came across this problem and found it interesting. I would like to see how others approached it.

Note: This is a IMO shortlist problem.

Note by Calvin Lin
5 years, 1 month ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

For each positive integer n, find the number of odd coefficients in the expansion of (x2+x+1)n. ( x^2+x+1)^n.

Let f(n) be the desired number of odd coefficients in (x2+x+1)n. ( x^2+x+1)^n.

... I will be using n=6039 as an example:

1) Write n in base 2 ... 6039=10111100101112.6039 = 1011110010111_2.

Definition: a 1_string is a string of 1's of maximal length in a base 2 number.

For example: 6039 has 4 1_strings. Their lengths are 1, 4, 1 and 3, resp.

2) Examine n's 1's to find all of its 1_strings.

Define f_values for the 3 types of 1_strings:

. a 1_string of length 1 has an f_value of 3.

. a 1_string of even length, le, has an f_value of (2le+21)/3. (2^{le+2}-1)/3.

. a 1_string of odd length, lo, has an f_value of (2lo+2+1)/3. (2^{lo+2}+1)/3.

Then f(n) = product of the f_values of n's 1_strings.

For n=6039:

Since 6039's 1_strings have lengths of 1, 4, 1 and 3 resp.

Their f_values are 3, 21, 3 and 11, resp.

So f(6039) = 3 X 21 X 3 X 11 = 2079.

Excellent problem ...

I found pretty quickly that for all n>=0, f(2n)=3.f(2^n) = 3.

After that I made little further progress, I decide to research the problem. I found, online the book

(PDF) Enumerative Combinatorics by Richard Stanley where I found how to compute f(n).

Michael Fischer - 5 years ago

Log in to reply

I cheated a little bit (ok, a lot):

http://oeis.org/A071053

I don't see anything like a closed-form formula. This paper seems to be all about finding this function's asymptotics:

http://arxiv.org/abs/0802.2654

I can show that the answer is 3 3 if n n is a power of 2 2 . :)

Patrick Corn - 5 years, 1 month ago

Log in to reply

There is a way to define the number of coefficients in a closed form formula, i.e. only depends on the value of nn.

Calvin Lin Staff - 5 years, 1 month ago

Log in to reply

I get Coefficient of xr=k=0r/3(1)k(n+33k1r3k)(nk)\text{Coefficient of} \ x^r=\displaystyle\sum_{k=0}^{\lfloor r \rfloor /3} (-1)^k \dbinom{n+3-3k-1}{r-3k} \dbinom{n}{k} where r\lfloor r \rfloor is the greatest multiple of 33 less than or equal to rr, and r{0,1, ... ,2n}r \in \{0,1, \ ... \ ,2n \} .

How do we know how many of these monsters are odd?

Pratik Shastri - 5 years, 1 month ago

Log in to reply

Note that you are not asked to find explicitly which ones are odd, just the total number of them that are odd.

For example, if we were merely dealing with (x+1)n (x+1)^n , then it is a well known result that the number of odd coefficients is 2b 2^b , where bb equals the number of 1's in the binary representation of nn. There can be several ways to show this, one of which includes finding explicitly which terms are odd (using Lucas Theorem).

Calvin Lin Staff - 5 years, 1 month ago

Log in to reply

I got a somewhat similar result.Is there an easy way to see if a binomial is odd or even?

Bogdan Simeonov - 5 years, 1 month ago

Log in to reply

So...

(x2+(x+1))n(x^2+(x+1))^n? Hmmmmm.... the answer will be in terms of x. Can't wait to see the solutions (wish had time to solve it)!

John Muradeli - 5 years, 1 month ago

Log in to reply

The answer will be in terms of nn.

For example: If n=1 n = 1 , then we have x2+x+1 x^2 + x + 1 , which has 3 terms of odd coefficients.
If n=1 n = 1 , then we have (x2+x+1)2=x4+2x3+3x2+2x+1 (x^2 + x + 1)^2 = x^4 + 2x^3 + 3x^2 + 2x + 1 , which has 3 terms of odd coefficients.
If n=3 n = 3 , then we have (x2+x+1)3=x6+3x5+6x4+7x3+6x2+3x+1 (x^2 + x + 1) ^3 = x^6 + 3x^5 + 6x^4 + 7x^3 + 6x^2 + 3 x + 1 , which has 5 terms of odd coefficients.

Calvin Lin Staff - 5 years, 1 month ago

Log in to reply

Oh I see... only thought of x because in expansion of form (variable+number)^N the number shapes the coefficients. But I never thought out the number theory rules of oddodd, oddeven etc. Yes the answer may be (or, like you said, will be) in terms of n. And now it'll be great to see why it's n+2n+2 (or maybe not ;))

John Muradeli - 5 years, 1 month ago

Log in to reply

Can you say more things about IMO problems I just heard about them from this note. How can you post a solution?

Adrian Neacșu - 5 years, 1 month ago

Log in to reply

Well, using trinomials I found the formula for the coefficients but it's a sum of trinomials and I can't find any easy parity criteria for that.

Bogdan Simeonov - 5 years, 1 month ago

Log in to reply

Or maybe if we denote knk_n the coeff of x^k in the polynomial, we can get that kn=i=1n1(k1)i+(k2)i\displaystyle k_n=\sum_{i=1}^{n-1} (k-1)_i+(k-2)_i

Bogdan Simeonov - 5 years, 1 month ago

Log in to reply

Calvin My questions are not been rated yet They have been uploaded 3days before Plz give me your e mail id so that i can contact you Your's faithfully Jai gupta

Jai Gupta - 5 years, 1 month ago

Log in to reply

It is a lot easier for your problems to be rated if you state the topic and the (perceived) level of the problem. Note that it also depends on the number of people who have viewed and answered your problem.

I typically do not like "Find this pattern" unless it is very obvious, since there are numerous ways of justifying the next term (e.g. there is always a polynomial which satisfies any finite sequence). I appreciate seeing your solutions, but I don't understand them. Can you please reply to my comments? Thanks.

Calvin Lin Staff - 5 years, 1 month ago

Log in to reply

Kkk Calvin now i will not upload that type questions which are controversial Satvik also told me the same but love mat thats why i was uploading but now ill not

Calvin please see my question assertion and reason   
     Is it suitable or not

Jai Gupta - 5 years, 1 month ago

Log in to reply

@Jai Gupta The question is fine.

I have a question about it through, please reply to my comment in your solution.

Calvin Lin Staff - 5 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...