Шелковый путь олимпиада по математике 2016 года | Казахстанские олимпиады

Пусть $P(n)$ это количество способов разбить натуральное число $n$ на сумму степеней двойки, при этом порядок не имеет значение. Например $P(5) = 4$, так как $5=4+1=2+2+1=2+1+1+1=1+1+1+1+1$.

Докажите, что для любого натурального $n$ верно тождество