Câu hỏi 37
Gọi $P(n)$ là số cách phân tích số nguyên dương $n$ thành tổng các lũy thừa của $2$, trong đó thứ tự các số hạng không quan trọng. Ví dụ, $P(5) = 4$, vì $5 = 4+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1$. Chứng minh rằng với mọi số nguyên dương $n$, đẳng thức sau đúng:
$$
P(n) + (-1)^{a_1}P(n-1) + (-1)^{a_2}P(n-2) + \dots + (-1)^{a_{n-1}}P(1) + (-1)^{a_n} = 0,
$$
trong đó $a_k$ là số chữ số $1$ trong biểu diễn nhị phân của $k$.
$$
P(n) + (-1)^{a_1}P(n-1) + (-1)^{a_2}P(n-2) + \dots + (-1)^{a_{n-1}}P(1) + (-1)^{a_n} = 0,
$$
trong đó $a_k$ là số chữ số $1$ trong biểu diễn nhị phân của $k$.