MathDB

4

Part of 2016 Silk Road

Problems(1)

P(n)+(-1)^{a_1}P(n-1)+(-1)^{a_2}P(n-2)+...+(-1)^{a_{n-1}} P(1)+-1)^{a_n} = 0

Source: SRMC 2016 P4

9/2/2018
Let P(n)P(n) be the number of ways to split a natural number nn to the sum of powers of two, when the order does not matter. For example P(5)=4P(5) = 4, as 5=4+1=2+2+1=2+1+1+1=1+1+1+1+15=4+1=2+2+1=2+1+1+1=1+1+1+1+1. Prove that for any natural the identity P(n)+(−1)a1P(n−1)+(−1)a2P(n−2)+…+(−1)an−1P(1)+(−1)an=0,P(n) + (-1)^{a_1} P(n-1) + (-1)^{a_2} P(n-2) + \ldots + (-1)^{a_{n-1}} P(1) + (-1)^{a_n} = 0, is true, where aka_k is the number of units in the binary number record kk .
[url=http://matol.kz/comments/2720/show]source
binary representationnumber theorypower of 2combinatorics