Q4 Matemática (Silk Road 2016)

04 | Silk Road | 2016 | Matemática

Seja $P (n)$ o número de maneiras de dividir um número natural $n$ pela soma de potências de dois, quando a ordem não importa. Por exemplo $P (5) = 4$ , como $5 = 4 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1$ . Prove que para qualquer natural a identidade $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,$ é verdadeiro, onde $a_{k}$ é o número de unidades no registro de número binário $k$ . fonte