Let $n$ be a positive integer. Find the number of odd coefficients of the polynomial $(x^2-x+1)^n$.
Problem
Source: 2016 Taiwan TST Round 3
Tags: algebra, number theory, polynomial
21.07.2016 20:07
Is it same problem with this and replace $x$ by $-x$ $?$
21.07.2016 20:13
ThE-dArK-lOrD wrote: Is it same problem with this and replace $x$ by $-x$ $?$ I would say so because the number of odd coefficients depends on the parity of the coefficient, not if it's negative or positive (the difference of an odd number and an even number would be the same parity (odd) as the sum of a odd number and a even number). Thanks for the solution!
21.07.2016 20:36
The above link isn't really a full solution, as many of the details are left out are unclear, and besides, it's beautiful enough of a result that I'll post a solution here.
22.07.2016 07:36
Also see here http://www.artofproblemsolving.com/community/c6h1254886p6505703
11.07.2021 12:26
Here is a solution with combinatorial flavors. Let $A(n)$ be the answer we want, $B(n)$ be the number of blocks with consecutive $1$ in the expansion of $(x^2+x+1)^n$ (e.g. $(x^2+x+1)^3 = x^6+x^5+x^3+x+1$, so $B(3) = 3$ since there are three blocks $5, 6$; $3$; $1, 2$ ). It follows that Claim 1. For $n \in \mathbb{N}$, we have $B(2n) = A(2n) = A(n)$ Since $P(x^2) \equiv P(x)^2 \pmod 2$ holds for all $P \in \mathbb{Z}[x]$, the result is trivial. $\square$ Claim 2. For $n \in \mathbb{N}$, we have $B(2n+1) = A(n)$ and $A(2n+1) = A(n) + 2B(n)$ It comes to the key point of this problem. Consider a blocks with $k$ consecutive $1$ in $(x^2+x+1)^n$, like (we ignore variables since they are not important) \[ 0, \underbrace{1, 1, \ldots, 1}_{k} 0 \]After squaring the polynomial it becomes \[ 0, 0, 0, \underbrace{1, 0, 1, 0, \ldots, 1}_{k\ \text{of}\ 1}, 0, 0, 0\]and there are at least three $0$ between two blocks, hence multiplying $(x^2+x+1)$ does not make the blocks interact with each others. After multiplying $(x^2+x+1)$, this block becomes \[ 0, 1, 1, \underbrace{0, 1, 0, \ldots, 0}_{k-2\ \text{of}\ 1}, 1, 1, 0, 0, 0 \]So for each blocks, they divided into $k$ blocks, and with $k+2$ of $1$. Hence $B(2n+1) = A(n)$ and $A(2n+1) = A(n) + 2B(n)$. $\square$ Now let the binary representation of $n$ contain $k$ blocks of consecutive $1$, and each blocks with length $l_1, l_2, \ldots, l_k$. We induct on $k$ to show that \[ A(n) = \prod_{i=1}^k \left(\frac{4\cdot 2^{l_i}-(-1)^{l_i}}{3} \right) \] Assume the statement holds for $k-1$, (there is no need for basis. In fact, let $A(0) = 1$, and the statement below is also true). Let $n = 2^{l_1+1}m + 2^{l_1}-1$. For $i = 0, \ldots, l_1$, define \[ c_i \coloneqq A(2^{i+1}m +2^i-1) \]\[ d_i \coloneqq B(2^{i+1}m +2^i-1) \]Then it follows the recurrence relationship \[ d_i = c_{i-1} \quad \forall \ i = 1, \ldots, l_1 \]\[ c_i = c_{i-1} +2d_{i-1} = c_{i-1} +2c_{i-2} \quad \forall \ i = 2, \ldots, l_1 \]And note that $c_0 = d_0 = A(m)$, $c_1 = c_0 +d_0 = 3c_0$. By the recurrence relation above one can show that \[ c_k = \left(\frac{4\cdot 2^k - (-1)^k}{3} \right) c_0 \]And for $k = l_1$ we have \[ A(n) = \left(\frac{4\cdot 2^{l_1} - (-1)^{l_1}}{3} \right)A(m) \]Apply inductive hypothesis on $m$ then we're done. So by mathematical induction, the answer is \[ A(n) = \prod_{i=1}^k \left(\frac{4\cdot 2^{l_i}-(-1)^{l_i}}{3} \right) \]Q.E.D. $\blacksquare$