Let $ n$ be a positive integer. Find the number of odd coefficients of the polynomial \[ u_n(x) = (x^2 + x + 1)^n. \]
Problem
Source: IMO ShortList 1988, Problem 2, Bulgaria 3, Problem 3 of ILL
Tags: algebra, polynomial, function, binomial coefficients, generating functions, IMO Shortlist
MellowMelon
18.07.2009 02:12
Work in $ (\mathbb{Z}/2\mathbb{Z})[x]$, so $ (x^2 + x + 1)^2 = x^4 + x^2 + 1$ for instance. If $ (x^2 + x + 1)^n = x^{a_1} + x^{a_2} + \cdots + x^{a_k}$, then $ (x^2 + x + 1)^{2n} = x^{2a_1} + x^{2a_2} + \cdots + x^{2a_k}$. Use this and multiplication by $ x^2 + x + 1$ (once at a time) to construct $ (x^2 + x + 1)^n$ for any $ n$.
The end result is the following: write $ n$ in binary. Suppose for all $ i$ there are $ e_i$ consecutives strings of $ 1$s with length $ i$ (so $ 101111001101$ has $ e_1 = 2, e_2 = 1, e_3 = 0, e_4 = 1$ and rest $ 0$). Then the answer is $ f(1)^{e_1} f(2)^{e_2} f(3)^{e_3} \cdots$, where $ f(n)$ is some function that you get by solving a linear recurrence.
admire9898
20.07.2009 13:14
Thanks for the solusion
SCP
02.06.2011 21:15
MellowMelon wrote:
Work in $ (\mathbb{Z}/2\mathbb{Z})[x]$, so $ (x^2 + x + 1)^2 = x^4 + x^2 + 1$ for instance. If $ (x^2 + x + 1)^n = x^{a_1} + x^{a_2} + \cdots + x^{a_k}$, then $ (x^2 + x + 1)^{2n} = x^{2a_1} + x^{2a_2} + \cdots + x^{2a_k}$. Use this and multiplication by $ x^2 + x + 1$ (once at a time) to construct $ (x^2 + x + 1)^n$ for any $ n$.
The end result is the following: write $ n$ in binary. Suppose for all $ i$ there are $ e_i$ consecutives strings of $ 1$s with length $ i$ (so $ 101111001101$ has $ e_1 = 2, e_2 = 1, e_3 = 0, e_4 = 1$ and rest $ 0$). Then the answer is $ f(1)^{e_1} f(2)^{e_2} f(3)^{e_3} \cdots$, where $ f(n)$ is some function that you get by solving a linear recurrence.
Some f(n)??? What do you/he mean?
Yabadabadou
02.05.2018 11:33
I think f(n) can get from n=1,2,3...it just a linear recurrence.
LittleKesha
02.05.2018 11:38
Sorry if I don't know it, but what mean "Work in $ (\mathbb{Z}/2\mathbb{Z})[x]$," ?
nikolapavlovic
02.05.2018 11:54
Means you're doing polynomials with coefficients from $\mathbb{F}_2$ and addition and multiplication of polynomials is over $\mathbb{F}_2$ as well.
LittleKesha
02.05.2018 12:29
mmm... thanks but what mean $\mathbb{F}_2$ ??
integrated_JRC
02.05.2018 13:00
Maybe some stuffs from Field Theory.
LittleKesha
02.05.2018 13:37
ok, some links where I can find a simple explication or introduction? What are the prerequisities?
nikolapavlovic
02.05.2018 15:08
Basically everything you do with coefficients is mod 2 so fro example $x^2+1+(x^2+3)=0$ $x^2+x+1=x^2-x+1$ etc. but you get the point. This is quite cool cause over any field (not necessarily over mod 2) you can do stuff with these polys such as factor them,pop derivative on them check if they're reducible and so on.Polynomial over any field act "nicely" for example see this
Anigasan1328
15.06.2018 19:19
Could we just use generating functions to solve this
stronto
26.11.2018 07:42
Another solution sketch, maybe. $u_n$ is equivalent to the number of $1$s in the binary representation of $5^n$, which in turn is equal to the sum of the digits of the number, which we will denote as $s_2(n)$. By Legendre's, we have $\sum_{i=1}^{\infty} \lfloor \frac{5^n}{2^i} \rfloor = 5^n - s_2(5^n) \rightarrow s_2(5^n) = 5^n - \sum_{i=1}^{\infty} \lfloor \frac{5^n}{2^i} \rfloor$. There might be a way to simply this algebraically.